若一个数可以进行因数分解，则得到的两个数一定是有一个>=sqrt(x),另一个<=sqrt(x).
朴素算法
这个算法是最简单的素数判断算法+遍历素组，耗时长
bool judge(ll x) { if(x==2) return true; if(x<2||x%2==0) return false; for(int i=3;i<=sqrt(x+1);i+=2)//这个地方可以优化一下，一个是范围，一个是步长 （素数一定是奇数） { if(x%i==0) return false; } return true; }
埃氏筛
利用当前已经找到的素数，从后面的数中筛去当前素数的倍数，当前素数已经是筛去数的质因子，如此下去能筛除之后所有的合数，是一种比较快的筛法
美中不足是会筛除多次比如8和16，同时被2和4筛去
输入数据
100 2
2
91
输出数据
Yes
No
#include <bits/stdc++.h> using namespace std; int prime[10000005]; const int N = 10000000; void isprime() { fill(prime,prime + N,true); prime[1] = false; for(int i = 2; i <= N; ++i) { if(prime[i]) { for(int j = i * 2;j <= N;j += i) { prime[j] = false; } } } } int main() { isprime(); int n,m; cin>>n>>m; int num; for(int i = 0;i < m;i++) { cin>>num; if(prime[num]) cout<<"Yes\n"; else cout<<"No\n"; } return 0; }
欧式筛
这是一种很好的线性筛法，和埃氏筛法的区别是对于每一个要筛除的数，欧拉筛法只筛除一次。原理如下
任何一个合数都可以表示成一个质数和一个数的乘积
假设A是一个合数，且A = x * y，这里x也是一个合数，那么有:
A = x * y; (假设y是质数，x合数)
x = a * b; (假设a是质数，且a < x——>>a<y)
-> A = a b y = a Z (Z = b y)
即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积，那样我们到每一个数，都处理一次，这样处理的次数是很少的，因此可以在线性时间内得到解。
#include <bits/stdc++.h> using namespace std; int prime[10000005]; int primesize = 0; bool isprime[10000005]; void getlist(int listsize) { memset(isprime,1,sizeof(isprime)); isprime[1] = false; for(int i = 2;i <= listsize;i++) { if(isprime[i]) { prime[++primesize] = i; } for(int j = 1;j <= primesize && i * prime[j] <= listsize;j++) { isprime[i * prime[j]] = false; if(i%prime[j] == 0) break; } } } int main() { int n,m; cin>>n>>m; getlist(n); int num; for(int i = 0;i < m;i++) { cin>>num; if(isprime[num]) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } } return 0; }
