暴力筛选

这种方法我就不多说了，一个数是素数则其只能被1和它本身整除，抓住这个特性，从2开始遍历到这个数减1，如果该数能整除其中任意一个数，则其都不是素数，如果想筛选某个范围内的，则遍历这个区间，从左端点遍历到右端点，该数是素数则将其标记为0，遍历完以后，数组中是0的就是合数，非0是素数，时间复杂度On^2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 判断一个数是不是质数
    for(int i=2;i<n;i++){
        if(n%i==0){
            break;
        }
    }
筛选一个区间的质数
    memset(arr,1,sizeof arr);
    for(int j=x;j<=y;j++){
        for(int i=2;i<n;i++){
            if(n%i==0){
                arr[j]=0;
                break;
            }
        } 
    }
arr[i]=1则是质数否则是合数

  • 稍加优化

    对于一个数其因子一定是成对出现的，例如8的一对因子就是2和4，因此如果这个数能被2整除则不用判断能否被4整除了，对于一个合数来说这个性质没什么用，因为判断到能整除2就直接break了，但若该数是一个质数呢？那就会把该数从头到尾都遍历一遍，假若数据很大时，这是非常消耗时间的，我们就可以利用因子成对的性质，遍历到根号n，为什么是根号n，举个例子，25，一对因子对是5 5，5相当于一个分界线，其他的因子一定一个大一个小，这样就优化了这个算法，时间复杂度是On^3/2
1
2
3
4
5
for(int i=2;i*i<=n;i++){ //注意这里判断条件是<=
    if(n%i==0){
        break;
    }
}

素筛

注意：素筛必须从1开始筛，实质上是一个打表

  • 埃式筛

    学习素筛之前我们要知道一个任意一个合数都可以转换成为一个质数和某个数的乘积，例如25可以转换成55，偶数可以转换成2a，这样我们其实可以利用这个性质将一个区间内的所有质数的倍数都标记一下，被标记的数就是合数，剩下的就是质数
1
2
3
4
5
6
7
8
9
10
11
12
13
int p[1000]; //p数组用来存储质数
void prime()
{
    vis[1]=1; //1不是质数
    for(int i=2;i<=n;i++){ //n是筛选的范围
        if(!vis[i]){
            p[++cnt]=i; //存储质数
            for(int j=2*i;j<=n;j+=i){  //这里可以有一个优化，j=2*i
                vis[j]=1; //标记质数的倍数
            }
        }
    }
}

  • 欧拉筛

    上面讲的埃式筛有一个非常大的缺陷，就是会重复标记，例如12，我们首先用2的6倍标记了它，之后又用了3的4倍再次标记，这样就造成了时间的浪费，而素筛本身就是因为时间上的优化才出现的，因此这点必须优化，因此出现了欧拉筛，欧拉筛就是为了解决重复标记的问题

对于vis[i*p[j]] = 1 的解释： 这里不是用i的倍数来消去合数，而是把 p里面纪录的素数，升序来当做要消去合数的最小素因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int vis[maxn],p[maxn/10]; //质数密度不大，除以10可以减少空间浪费
int cnt=0;
void prime()
{
    vis[1]=1;
    for(int i=2;i<=maxn;i++){
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&i<=maxn/p[j];j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break; //核心代码，如果i能整除这个质数则跳出循环
        }
    }
}
对于 i%p[j] == 0 就break的解释 ：当 i是[j]的倍数时，i = kp[j]，如果继续运算 j+1，i * p[j+1] = p[j] * k p[j+1]，这里p[j]是最小的素因子，当i = k * p[j+1]时会重复，所以才跳出循环。
举个例子 ：i = 8 ，j = 1，p[j] = 2，如果不跳出循环，p[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。