共计 1336 个字符，预计需要花费 4 分钟才能阅读完成。
素数
@(算法)
素数简介
质数（prime number）又称素数。质数定义为在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数。还能被其他数（0 除外）整除的数为合数。
判断一个数是否是素数根据定义，除了 1 和本身之外没有其他约束，所以判断是否为质数，根据定义直接判断从 2 到 n - 1 是否存在 n 的约数。
方法一：暴力破解！
bool isPrime(int num){
for(int i=2;i<num;i++){
if(num%i ==0){
return 0;
}
}
return 1;
}
上述方法，明显存在效率极低的问题。一个数若可以进行因式分解，那么分解时得到的两个数，一定是一个小于等于 sqrt(n)，一个大于等于 sqrt(n)
改进：
bool isPrime(int num){
int t=sqrt(num);
for(int i=2;i<num;i++){
if(num%i ==0){
return 0;
}
}
return 1;
}
方法二：素数筛法
可以提前处理出来 1~n 的全体素数
1. 把 1~n 列出来
2. 去掉不是特殊的 1
3. 从小到大，枚举每一个没有删掉的数字 i 把 i 的 2 倍，3 倍，4 倍，…, 删掉剩下的没被删掉的都是素数
const int N=100;
int notprime[N];
int main(){
notprime[1]=1;
for(int i=2;i<N;i++){
if(notprime[i]==0){
for(int j=i+i;j<N;j=j+i){//// 删掉 2 *i,3*i,4*i……
notprime[j]=1;
}
}
}
for(int i=1;i<N;i++){
if(notprime[i]!=1){
printf(“%d\t”,i);
}
}
return 0;
}
方法三：欧拉筛法
在素数筛法中，有很多合数被删除多次。而欧拉筛法提供两个数组，一个是素数表，另一个是删除合数表 (值为 1 表示表示不是素数)。
const int N=100;
int notprime[N]; // 删除标记, 值为 1 表示表示不是素数
int prime[N]; // 素数表
int main(){
int t=0; // 初始化素数表为空
notprime[1]=1;
for(int i=2;i<N;i++){
if(notprime[i]==0){// 找到一个没有被删除的数
prime[t++]=i; // 加入素数表
}
for(int j=0;j<t&&prime[j]*i<N;j++){// 枚举素数表
notprime[prime[j]*i]=1;
if(i%prime[j]==0){
break; // 保证了每个合数只会被它的最小素因子筛掉
}
}
}
for(int i=0;i<N;i++){
if(prime[i]!=0){
printf(“%d\t”,prime[i]);
}
}
}
prime[] 数组中的素数是递增的, 当 i 能整除 prime[j]，那么 prime[j]*i 这个合数肯定被 prime[j] 乘以某个数筛掉。i%prime[j]== 0 保证了每个合数只会被它的最小素因子筛掉。
参考 [1]http://www.cnblogs.com/zhuoha…[2]http://www.cnblogs.com/zhuoha…[3]https://baike.baidu.com/item/…
