求素数的几种算法

问题背景：最近在论坛上看见了关于素数的求解问题，所有收集了相关资料真理了几个常用的求素数的算法，希望对有兴趣的朋友提供方便

• （优化后的）基本算法
• 筛选法
• 6N+-1发（其实也是一种筛选法，只是构造的筛子更细了，提高了效率）

一、基本方法

• 方法描述：这种方法是通过n%i？=0,{i|2,3,...i*i=n}如果=0，那么n不是素数，结束本次循环

• 性能测试：num=50000,时间：80ms
• 总结：算法简单，但是效率其实还是挺搞的，因为在取模的时候，只要条件第一次不成立（n%m==0）那么就不再测试这个数，即跳出本次循环。算法的时间复杂度是很接近于O（n）的。

private static void prime(int num) {
		long start = System.currentTimeMillis();
		int m, n;
		label: for (n = 2; n <= num; n++) {
			for (m = 2; m * m <= n; m++) {
				if (n % m == 0) {
					continue label;
				}
			}
//太多了可能myeclipce中看不到打印结果，可以用num=100，测试
			System.out.print(n + " ");
		}
		System.out.println();
		System.out.print("时间：");
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

二、筛选法
算法描述：算法的思想是打表，先初始化一个数组{2,3,4,...,n}

我们以n=30为例
一、初始化表：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
二、把第一个数（2）取出来，去掉所有可以被2整除的数。
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
三、取第二个数（3），去掉所有可以被 3整除的数。
2 3 5 7 11 13 17 19 23 25 29
四、取第三个数（5），因为4已经被去除了，再去掉所有可以被5整除的数。
2 3 5 7 11 13 17 19 23 29
五、取第四个数（7）7*7>30所以停止。
• 性能测试：num=50000,时间：24680ms
• 总结：此算法在理论上的效率其实是挺高的，但是实际在实现时是不可取的。

private static void prime3(int n) {
		long start = System.currentTimeMillis();
		List<Integer> list = new LinkedList<Integer>();
		for (int i = 2; i <= n; i++) {
			list.add(i);
		}
		for (int j = 0; j < list.size() && list.get(j) * list.get(j) <= n; j++) {
			for (int k = 0; k < list.size(); k++) {
				if ((list.get(k) != list.get(j))
						&& list.get(k) % list.get(j) == 0) {
					list.remove(k);
				}
			}
		}
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + " ");
		}
		System.out.println();
		System.out.print("时间：");
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

三、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为自然数)。 根据上述分析，我们可以构造另一面筛子，只对形如6
N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。
在程序上，我们可以用一个二重循环实现这一点，外循环i按3的倍数递增，内循环j为0－1的循环，则2(i+j)-1恰好就是形如6N±1的自然数。
• 性能测试：num=50000,时间：50ms
• 总结：此算法，其实也是一种筛选算法，只是筛子更细，能够将整数中大约2/3的数筛选出去。所以效率很高

private static void prime2(int num) {
		long start = System.currentTimeMillis();
		for (int n = 2; n <= 3; n++) {
			System.out.print(n + " ");
		}
		label1: for (int n = 1;; n++) {
			label2: for (int m = 0; m <= 1; m++) {
				int tmp = 2 * (3 * n + m) - 1;
				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.out.print("时间：");
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

评论

2 楼 heisedeyueya 2011-09-19  

SMCwwh 写道

方法2，可以有更好的实现。

这个是我个人的实现方法，其实这种方法本身是不可取的，因为链表的访问本身是比较耗费时间的，我是为了实现这个算法本身而写的实现，希望可以看到更好的实现，您有什么好的思路希望能分享一下

1 楼 SMCwwh 2011-09-19  

方法2，可以有更好的实现。