恼人的素数
连羽疲倦的推开公主阁的门，“啊啊啊，怎么会留这么麻烦的作业。”
“既然布置了，那就没有办法了啊，今晚一起算就好了。”连辰拍了拍连羽的背，表示鼓励。
荆盈将做好的菜端到餐桌上，看着勉强露出笑容的两人问道：“所以你们老师布置了什么题啊？”
“关于素数的题，老师给了一个很大的数，问是不是素数。”连辰解释道。
“素数啊，我到是知道些比较快的判断方法。”
“真的？”连羽如同见了救星一般。
作为立志要成为计算机天才的你们，能帮助连羽么？
输入格式:
多组测试
每组测试有一行，为一个正整数k(k < 10^9)，
输出格式:
每组测试输出一行，
若k为素数，输出“Yes”，否则输出“No”
时间限制1000ms
此题为判断一个数是否为素数，多组测试数据，注意k<10^9，首先用筛选素数法开不了那么大的数组，如果用普通的for循环判断从2到根号k是否能整除k一定会T，所里要加一个优化，如果判断了2不能被整除，那么4，6，8，10…等2的倍数都不用判断了，因为一定不会被k整除，同理3的倍数，5的倍数都不用判断了，所以只需要判断2至根号10^9里的所以素数就可以了，提前打个表
#include<stdio.h>
#include<math.h>
bool a[40000];
void init(){
for(int i = 2;i <= 35000;i++){
if(!a[i]){
for(int j = 2 * i;j <= 35000;j += i){
a[j] = 1;
}
}
}
}
int main(void){
int k;
init();
while(scanf("%d",&k)!=EOF){
if(k == 1){
printf("No\n");
continue;
}
int flag = 1;
for(int i = 2;i <=sqrt(k) ;i++){
if(a[i]==0 && k % i == 0){
flag = 0;
break;
}
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}
版权声明：本文为GYH0730原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。