Java 求素数运算
网络上对求素数之解数不胜数，我在此总结归纳一下，同时对一些编码，加以改进，效率有成倍热提高。第一种：
原理: 6N(+-)1法
任何一个自然数，总可以表示成为如下的形式之一： 6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以， 除了2和3之外， 所有的素数都可以表示成6N±1的形式(N为自然数)。 根据上述分析，我们可以构造另一面筛子， 只对形如6N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。
在程序上，我们可以用一个二重循环实现这一点，外循环i按3的倍数递增，内循环j为0－1的循环，则2(i+j)-1恰好就是形如6N±1的自然数。
源码：
private static void method3(int num) { long start = System.currentTimeMillis(); label1: for (int n = 1;; n++) { label2: for (int m = 0; m <= 1; m++) { int tmp = (3 * n + m)<< 1 - 1; //这里用位移"<<1"代替"*2" ，效率会有明显提高 if (tmp > num) break label1; for (int k = 2; k * k <= tmp; k++) if (tmp % k == 0) if (m == 0) continue label2; else continue label1; System.out.print(tmp + " "); } } System.out.println("耗时："+(System.currentTimeMillis()-start)); }
测试结果： num = 50 0000;运行100次取平均值:
耗时：223
第二种：
public long method4(int num) {long bTime = System.currentTimeMillis();ArrayList<Integer> al = new ArrayList<Integer>(num>>1); //申请预计空间,避免扩容 for (int i = 2; i <= num; i++) { boolean ok = true; for (int t : al) { // 用已有质数集作判断,减少比较次数 if (i % t == 0) { ok = false; break; } if (t * t > i) { // 这句很关键,用小于其平方根的数整除 break; } } if (ok) { al.add(i); } } return System.currentTimeMillis()-bTime;} 测试结果： num= 50 0000; 运行100次取平均值：
耗时：376
页:
[1]