素数——朴素筛法及其优化:埃氏筛法 #质数(素数)"/>
[笔记] 筛素数——朴素筛法及其优化:埃氏筛法 #质数(素数)
朴素筛法
从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(大概)
埃氏筛法
- 朴素做法的优化:埃氏筛法。(此算法由一个埃及人发明,所以叫 埃氏筛法)
原理:当i不是质数时,没必要筛掉它的倍数,因为它的吧倍数将会是其它质数的倍数。- 筛到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)一个级别
更多推荐
[笔记] 筛素数——朴素筛法及其优化:埃氏筛法 #质数(素数)
发布评论