普通素数筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//bitset 被置1说明是素数
public static void count(BitSet set){
	//length() -> Returns the "logical size" of this BitSet
	for(int i = 2; i < set.size(); i++){
		//初始化，全部置1
		set.set(i);
	}
	for(int i = 2; i * i < set.size(); i++){
		if(set.get(i)){
			for(int j = 2 * i; j < set.length(); j += i){
				//素数的倍数全部标记为非素数
				set.clear(j);
				
			}
		}
	}
}

线性素数筛法

上面的筛选方法中，可以看出，有很多重复
比如30，会被2,3,5都标记，这样重复很多次
下面的方法所有数字只会被标记一次，是线性的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void main(String[] args) {
	final int N = 100000;
	boolean[] isNot = new boolean[N];
	int[] prime = new int[N];
	int cnt = 0;
	for(int i = 2; i < N; i++){
		if(!isNot[i]){
			prime[cnt++] = i;
		}
		//1.每个数字都会经过这循环
		//a.如果是素数，就标记素数的素数倍数，即k=p1*p2，而p1,p2都是不相同的素数，一定不会重复筛选
		//b.如果是合数，就只晒出该数字和最小素数的乘积，这样筛选才不会重复。
		//因为一个合数是若干素数的乘积，因为筛选过程不重复，因此只会被最小素数和另一数字乘积时选住
		for(int j = 0; j < cnt && prime[j] * i < N; j++){
			isNot[i * prime[j]] = true;
		//	System.out.println("i * prime[j] = "+i+"*"+prime[j]+" = "+i * prime[j]);
			//2.该合数是素数的倍数就退出筛选
			if(i%prime[j] == 0){
				break;
			}
		}
		
	}
}

关键之处在于2，保证了每个数字筛选一次，因为只会被其最小的素数因子筛选到！
这里所有合数都可以表示成若干个素数的乘积