[数据结构与算法]素数的筛选方法

埃氏筛法：

其实就是先将2~n的整数写下，依次将最小数的的倍数划去

比如先是2，然后将2的倍数（4、6、8、10...）划去，紧接着是3，划去3的倍数（6、9、12、15...）以此类推。如此反复就能枚举你n以内的素数。

以第十万零二个素数是多少为题。

埃筛法需要先将x个数进行存储，对于开辟空间开多了浪费，少了不够。此时由素数定理可知：

给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n。

也就是说在不大于n的自然数里，总共的素数为 n/ln?n。

那么我们所开辟的数组长度可以为： n/ln?n。

代码如下：

/*
*自然数n之内的素数个数n/ln（n）
*/
public class Main{
    public static void main(String[] args){
        long now=System.currentTimeMillis();
        m1(100000);   
        System.out.println("耗时："+(System.curentTimeMillis()-now)+"ms");
    }
    /*求第N个素数*/
    private static void m1(int N){
        //N是第n个数
        //已知在整数x内大概有x/log（x）个素数
        //现在我们要逆推：要想求第N个素数，我们的整数范围是什么
        //n就是整数范围
        int n=2;
        while(n/Math.log(n)<N){
            n++;
        }
        //开辟一个数组，下标是自然数，值是标记
        //筛选法，把非素数标记
        int[] arr=new int[n];
        int x=2;
        while(x<n){
            if(arr[x]!=0){
                x++;
                continue;
            }
            int k=2;
            //对每个x，我们从2开始，对x的k倍，全部标记-1
            while(x*k<n){
                arr[x*k]=-1;
                k++;
            }
            x++;
        }
        //System.out.println(arr);
        //筛完后，这个很长的数组里面非素数下标对应的值都是-1
        int sum=0;
        for(int i=2;i<arr.length;i++){
            //是素数，计数+1
            if(arr[i]==0){
                sum++;
            }
            if(sum==N){
                System.out.println(i);
                return;
            }
        }
    }
}