关于素数计算的算法总结

素数是指大于1的只能被1和其本身整除的数。迄今笔者总结方法有三

1.暴力算法：直接根据定义在2到n-1计算，是否会被整除；

#include<stdio.h>
int main(){
	int i,j;
	int n;
	int flag = 1;
	scanf("%d",&n);
	for(i = 2; i < n; i ++){
		if(!(n%i)){
			printf("No\n");
			flag = 0;
		}
	}
	if(flag) printf("Yes\n");
}

2.稍微聪明一点的暴力算法：由各种方法易证，当i在n的开方之前不能整除n时，则在n的开方后面一定不存在能整除n的整数，当然n开方是整数也要考虑一下，综上所述，上代码：

#include<stdio.h>
int main(){
	int i,j;
	int n;
	int flag = 1;
	scanf("%d",&n);
	for(i = 2; i*i <= n; i ++){//这个地方i*i会减少计算量；如用sqrt（）比较耗时间
		if(!(n%i)){
			printf("No\n");
			flag = 0;
		}
	}
	if(flag) printf("Yes\n");
}

3.挨筛（素数表发）：我们由定义可以知道，如果两个数（都不为1）相乘等于一个值，则这个值必定不为质数；故我们在第一个质数2开始，筛选即可，上代码：

#include<stdio.h>
#define N 1000001
int t[N] = {1,1};
int main(){
	int i,j;
	for(i = 2; i*i < N; i ++){//注意这个i*i要不然会容易溢出导致各种错误
		if(!t[i]){
			for(j = i*i; j < N; j += i){
				t[j] = 1;
			}
		}
	}
}

4.欧拉筛：

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Doted Wood
• 本文链接： http://example.com/2021/09/14/算法/关于素数计算的算法总结/
• 版权声明： 版权归博主所有，转载请说明来源