素数筛
定义
素数筛用于求出\([2,n]\)范围内的质数。
求解算法
埃拉托斯特尼筛法
思路与简单证明
将\([2,\sqrt n]\)范围内质数的所有\(\leq n\)的倍数筛掉,剩下的就是质数。
时间复杂度\(O(n\log\log n)\)。
实现
1 | // notpri[i] 为 true 时表示 i 不是质数 |
欧拉筛
思路与简单证明
枚举\([2,n]\)范围内的所有数\(i\),枚举\([2,i]\)范围内的所有质数\(pri_j\),将\(i\cdot pri_j\)筛掉;
枚举\(pri_j\)时,满足\(i\bmod pri_j=0\)时终止,因为此时\(i\)可以表示为\(pri_j\cdot x\),之后的数\(i\cdot pri_{j+k}\)可以表示为\(pri_j\cdot x\cdot pri_{j+k}\),已经被\(pri_j\cdot x\)筛掉了,这样可以完全避免一个数被重复筛掉。
时间复杂度\(O(n)\)。
实现
1 | void cal_pri(int n) |