[笔记] 筛素数——朴素筛法及其优化：埃氏筛法 #质数（素数）

朴素筛法

从2~n枚举 i,再从小到大枚举所有已知的质数 primes[j],筛掉合数 i*primes[j],遇到新的质数就入队==
枚举所有小于n的数i,将i的所有倍数筛掉。
筛完后剩下的数就是质数。

朴素做法
void get_primes(int n ){
    for(int i = 2; i <= n; i ++){
    	if(!st[i])
    		primes[cnt ++] = i;//如果是质数，入队
    	for(int j = i + i; j <= n; j +=i)
    		st[j] = 1;//删掉它的所有倍数
	}
}
时间分析：n/2 + n/3 +....+n/n = n log n（大概）

1
2
3
4
5
6
7
8
9
10
11

---

埃氏筛法

1. 朴素做法的优化:埃氏筛法。（此算法由一个埃及人发明，所以叫 埃氏筛法）
   原理：当i不是质数时，没必要筛掉它的倍数，因为它的吧倍数将会是其它质数的倍数。
2. 筛到N时，如果N没有被筛掉，就说在2~i-1中没有N的约数，所以N是质数。
   时间是O(n log n)约等于 O(n)（和O(n)一个级别）
   3.补充：质数定理：1~n当中有 n / logn 个质数

埃氏筛法
void get_primes(int n ){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) {
        	primes[cnt ++] = n;//没被筛掉，说明是质数
        	for(int j = i + i; j <= n; j += i)//干掉它的所有倍数
        		st[j] = 1;
        }	
    }
}
时间是O(n log log n)和O(n)一个级别
1
2
3
4
5
6
7
8
9
10
11