质数：大于一的自然数中，除了1和它本身外没有其他因数的数
大于2的偶数一定不是质数
暴力
bool isPrime(int x){if(x<=1)return false;for(int i=2;i<x;i++){if(x%i==0)return false;}return true;
}
O(N)
优化1：跳过偶数
bool isPrime(int x){if(x<=1)return false;if(x==2)return true;if(x%2==0)return false;for(int i=3;i<x;i+=2){if(x%i==0)return false;}return true;
}
仍然是O(N)
优化2：因数是成对出现的，一个因数小于sqrt(x)，另一个因数就大于sqrt(x)，只需要枚举到sqrt(x)
bool isPrime(int x){if(x<=1)return false;for(int i=2;i*i<=x;i++){if(x%i==0)return false;}return true;
}
O($N^{1/2}$)
埃氏筛法
唯一分解定理：一个合数可以分解成若干个质数的乘积
一个质数的倍数一定是合数
埃氏算法求一个范围n内的所有质数：
vector<int> primes; //存找到的质数
bool isPrime[maxNum]; //标记下标是否是质数void Ero(int n){memset(isPrime,true,n);isPrime[0]=isPrime[1]=false;for(int i=2;i<=n;i++){if(isPrime[i]==true){primes.push_back(i);for(int j=i+i;j<=n;j+=i){isPrime[j]=false;}}}
}
O(Nlog(logN))
缺点：合数被重复标记
欧拉筛法
规定每个合数只被其最小的质因数筛掉，每个数只处理一次（质数直接收集，合数只需标记一次），所以是O(N)
被一个最小质因数x筛掉的合数y，y>=x*x，被x筛掉的合数至少是x的x倍
反证：若y是x的k倍（k<x）
- 若k是质数，那么y就不该被比k还大的质数x筛掉
- 若k是合数，k还可以分解成更小的质数，y就应该被更小的质数筛掉
vector<int> primes; //存找到的质数
bool isPrime[maxNum]; //标记下标是否是质数bool Euler(int n){memset(isPrime,true,n);isPrime[0]=isPrime[1]=false;for(int i=2;i<=n;i++){if(isPrime[i]==true){primes.push_back(i);for(int j=i;j<=n;j++){ //枚举倍数int y=j*i; //y是i的j倍，j至少是i//若y中有比i更小的质因数，这个质因数在j里面bool flag=true;//枚举已收集的质数，找是否有比i更小的质因数for(auto p:primes){if(j%p==0){flag=false;break;}}if(!flag)continue; //i不是y的最小质因数else isPrime[y]=false; //i是y的最小质因数，标记}}}
}
复杂度没有降下来
枚举每个质数的倍数的循环可以合并到外层循环
vector<int> primes; //存找到的质数，升序
bool isPrime[maxNum]; //标记下标是否是质数bool Euler(int n){memset(isPrime,true,n);isPrime[0]=isPrime[1]=false;for(int i=2;i<=n;i++){if(isPrime[i]==true){primes.push_back(i);}//枚举所有已收集的质数,把i当作prime[j]的倍数for(int j=0;j<primes.size();j++){int x=i*primes[j];if(x>n)break;isPrime[x]=false; //primes[j]是x的最小质因数if(i%primes[j]==0) //保证合数只被最小质因数标记//当primes[j]是i的质因数，primes[j+1]*i的//最小质因数<=primes[j]而不是primes[j+1]，//不能保证合数只被最小质因数筛，所以退出循环break;}}
}
时间复杂度O(N)