首页 > 代码库 > 筛法求素数

筛法求素数

素数表在算法中经常会用到,所以掌握一种高效求解素数表的算法是很有必要的。


这里介绍一种算法:筛法。筛法的时间复杂度我不太清楚,但我知道是接近于 O(n) 的,比一般的求解素数的算法效率要高很多,其基本思想如下:

1、要得到 2 — n 之间的所有素数,先记录下 2 — n 之间的所有整数,用集合表示 A = { 2 , 3 , 4 , 5 , 6 …… n }

2、创建一张素数表 PrimeTable ,刚开始表中是空的。用集合表示 PrimeTable = { }

3、挑选出 A 中最小的数 min ,加入 PrimeTable 。删除 min 的所有倍数。第一次挑选的时候,min = 2 ,把 2 加入到PrimeTable中并删除 2 的所有倍数后,集合 A = { 3 , 5 …… n } ,PrimeTable = { 2 }

4、重复步骤 3 ,直到集合 A 空了为止。这时也就生成了 2 — n 之间的素数表 PrimeTable = { 2 , 3 , 5 …… }


参考代码:

public class PrimeTable {

	// 常量,为了表示2—10000这个范围
	static final int CONSTANT = 10000;

	// A[0]不用,下标代表的就是2—10000之间的某个数
	static final int[] A = new int[CONSTANT + 1];

	// 1229是因为事先我已经知道了2—10000之间有1229个素数,不知道的时候可以定义大一些
	static int[] PrimeTable = new int[1229];

	private static void createPrimes() {
		for (int i = 2; i <= CONSTANT; i++) {
			// A[i]==0代表i之前没有被删除,是个素数;A[i]==1代表之前被删除了,不是素数;不是素数也就没必要再计算了
			if (A[i] == 0) {
				// i是素数的时候,删除所有i的倍数,赋值为1代表删除
				for (int j = i * 2; j <= CONSTANT; j += i) {
					A[j] = 1;
				}
			}
		}

		// 上面的for循环已经把A中的素数下标代表的A[i]赋值为0,合数下标代表的A[i]赋值为1了
		// 下面的for循环就是把A中的所有素数放到素数表PrimeTable中了

		int k = 0;
		for (int i = 2; i <= CONSTANT; i++) {
			if (A[i] == 0) {
				PrimeTable[k++] = i;
			}
		}
	}

	// 主函数
	public static void main(String[] args) {
		createPrimes();

		for (int i = 0; i < PrimeTable.length; i++) {
			System.out.println(PrimeTable[i]);
		}
	}
}