求1到1000之间所有的素数

答案:2 悬赏:30

解决时间 2021-03-03 17:13

提问者网友：萌萌小主
2021-03-03 04:34

有一个经典的算法：列出所有的数后，从2开始（因为1不是素数），把2到1000之间所有2的倍数去掉，然后把3到1000之间所有3的倍数去掉，直到把999所有的倍数去掉，剩下的全部是素数。
有一个问题就是：为了简化，去掉倍数的运算可以只进行到31（根号1000的整数部分），即只要把2到31之间所有的数的倍数去掉，剩下的就是素数，为什么只要进行到31呢

最佳答案

二级知识专家网友：许你一世温柔
2021-03-03 06:01

如果算31以后的数的倍数，如1倍2倍。。。。。
到31倍已经被以前的数的倍数
包含的，如32的3倍已经被3的32倍包含了

就说明在31以前已经算过了，所以到31 就完了。

全部回答

1楼网友：滚刀废物浮浪人
2021-03-03 06:54

#include #include bool isprime(int n) { int s,i; //cout<<"请输入一个大于二的正整数："; //cin>>n; s=(int)sqrt(n); for(i=2;i<=s;i++) if(n%i==0) return false; return true;//cout<<"该数是素数！"; //else cout<<"概数不是素数！"; } void main() { int m; for(m=100;m<=999;m++) if(isprime(m)) cout<

我要举报

如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！