算法学习——素数筛法

素数：一个大于1的自然数，除了1和它本身以外不再有其他因数的数称为素数。

合数:一个大于1的自然数，除了1和它本身以外还有其他因数的数称为合数。

因数：整数a除以整数b（b≠0）的商正好是整数而没有余数，称b是a的因数。

一、试除法

一次次试看能不能被因子整除。

int is_prime(int n) { //这里用i<=n/i，防止溢出，如i=1e6 for (int i = 2;i <= n / i;i++) { if (n % i == 0) return 0; } return 1; }

二、埃式筛法——接近线性O（logN）

素数的倍数一定是合数。找出合数，剩下都是素数。

#include<iostream> #include<vector> using namespace std; const int n = 1e6 + 10; //创建一个bool数组来标记素数 //初始时假设所有数都是素数 vector <bool> isPrime(n + 1, true); int main() { //遍历2~sqrt(n)的所有数 for (int p = 2;p <= n / p;p++) { //如果p是素数 if (isPrime[p]) { //标记p所有的倍数为非素数 for (int i = p * p;i <= n;i += p) isPrime[i] = false; } } return 0; }

三、欧拉筛法——线性

埃式筛有一些重复标记，欧拉筛去除了这些标记。

整数唯一分解定理：任何大于1的正整数n都可以唯一分解为有限个质数的乘积，任何合数都有他对应的一个最小质因子。只通过这个最小质因子将其标记，这样就避免了重复标记。

每个数都只被它的最小质因数筛去。

#include<iostream> #include<bitset> using namespace std; const int maxn = 1e6 + 10; bitset<maxn> pri;//0为素数，1为合数 int primes[maxn]; int pp = 0; int main() { int N = 1e6; int cnt = 0; for (int i = 2;i <= N;i++) { if (!pri[i]) { primes[pp] = i; pp++; } for (int j = i;j <= pp;j++) { pri[primes[j] * i] = 1; if (i % primes[j] == 0) break; } } }