筛选法求素数

 

但是，当求很多素数的时候就不合理了，每个数都有遍历

今天发现这个筛选法很不错。

求limit内的所有素数

 

V1.0

步骤：

1：从2开始

2:2是素数，去除2的倍数的数

3:下一个数是3,则3是素数，去除所以3的倍数的数

4：下一个数是5，则5是素数，去除是5的倍数的数

《为什么不是4,4是2的倍数，已经去除》

5：就这样一直遍历下去

Java程序：

 

int[] setPrime1(int limit){        //prime 是保存的素数数组        //notPrime 是保存的是否是素数的下标                int prime[] = new int[limit];        boolean notPrime[] = new boolean[limit];//默认 false        // true  不是素数        // false 是素数        int p = 0;        for(int i=2;i

 

V2.0

思想：

1.2是素数

2.除以2余数是0的数不是素数，一次筛选

3.2中没有把3筛选掉，同样，除以3余数是0的筛选掉

4.2中已经把4筛选掉了，下一个数从5开始，

5.重复上面过程

Java程序：

int[] setPrime2(int limit){        int prime[]= new int[limit];        boolean isPrime = true;        //true 是素数        //false 不是素数        prime[0] = 2;        int p =1;        for(int i=3;i

 

V2.1

在V1.0中定义两个数组，一个是存放素数的数组，一个是根据下标索引找素数的数组

当在一般情况只需要第二个数组的时候，就可以优化程序

这里有点不好说，看程序吧

自己体会下就是了

上界limit已经用sqrt（limit）附近的值判断了是否是素数

boolean[] setPrime3(int limit){        int prime[] = new int[limit];        int p = 0;        int subLimit = (int)Math.sqrt(limit)+1;        boolean notPrime[] = new boolean[limit];        for(int i=2;i

 

所有程序

package codeforces;public class findprime {        void run(){        int limit=10000;        int[] prime = setPrime2(limit);        for(int i=0;i