埃式筛法

  • O(n*logn)

原理: 利用一个数组保存0-n的数据,未访问过的就是素数,每次素数从素数N开始,依次递加晒除非素数,直到最后剩下的都是素数

1
2
3
4
5
6
7
8
9
10
11
12
埃式 筛法
public int countPrimes(int n) {
    int res = 0;
    boolean[] flag = new boolean[n+1];
    for(int i=2;i<n;i++){
        if(!flag[i]) res++;
        for(int j=2*i;j<n;j+=i){
            flag[j] = true;
        }
    }
    return res;
}

欧式筛法

  • O(n)

原理: 在埃式筛法的基础上排除那些重复筛选的计算.

prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 iprime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。
在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,prime[j]必定是prime[j]i的最小因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 欧式 筛法
 public int countPrimes(int n) {
    byte[] check = new byte[n];//用来标记是否已经访问过了，如果访问过了就打1，没访问过打0
    int[] primeList = new int[n]; //用来记素数

    int count = 0;//用来记录素数个数
    for(int i = 2;i< n;i++) {
        if(check[i]==0) {    //打了1的就不会再看了，重复赋值浪费时间
            primeList[count++] = i; //count变量记录素数个数，数组记录已知的素数的值
        }

        for(int j=0;j<count&&i*primeList[j]<n;j++) {
            check[i*primeList[j]] = 1; //标记 x=i*primeList[j],x位置是我访问过的位置，打1
            if(i%primeList[j]==0) {   //这一部分不好理解，比方说6，之前访问过（2,3），那么6%2==0,不用再检查6%3了，真正负责记录数据的是count变量
                break;
            }           
        }          
    }  
    return count;   
 }

普通优化筛法

原理: 只用遍历到i到sqrt(n),每遇到一个质数,从 i平方 开始以 步进为i 的筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 普通优化 筛法    
public int countPrimes(int n) {
    boolean[] nums = new boolean[n];
    //只需要遍历到n的平方根
    int sqrt = (int)Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++) {
        if (!nums[i]) {
            for (int j = i * i; j < n; j += i) {
                nums[j] = true;
            }
        }
    }
    int res = 0;
    for (int i = 2; i < n; i++) {
        if (!nums[i]){
            res++;
        }
    }
    return res;
}

经过试验对比，欧式筛和普通优化的筛法拥有相似的速度，而普通优化更利于理解，所以推荐使用最后一种方法