(谭c++5.1)筛选法求100之内的素数
程序员文章站
2022-03-13 12:21:17
...
筛选法指的是“埃拉托色尼(Eratosthenes)筛选法”。他是古希腊著名数学家。他采取的方法是:在一张纸上写上1~1000全部整数,然后逐个判断他们是否为素数,找出一个非素数就把他挖掉。最后剩下的就是素数。
具体做法:
- 先将1挖掉
- 用2去除它后面的个数,把能被2整除的数挖掉,即挖掉2的倍数
- 用3去除他后面的各个数,挖掉3的倍数
- 分别用4、5......各数作为除数去除这些数以后的各个数。这个过程一直进行到在除数后面的数已全部被挖掉为止。(事实上,可以简化,如果需要找1~n范围内的素数表,只需进行到除数为sqrt(n)取其整数)
上面的算法可以表示为:
- 挖去1
- 用下一个未被挖去的数p去除p后面各数,挖掉p的倍数
- 检查p是否小于根号n的整数部分,如果是,则返回2继续执行,否则就结束
- 纸上剩下的数就是素数
#include <iostream>
#include<cmath>
using namespace std;
int main()
{
int a[101];
a[0]=0; a[1]=0;
for(int i=2;i<=100;i++)
a[i]=i;
int j,k;
for(j=2;j<sqrt(100);j++)
for(k=j+1;k<101;k++)
{
if(a[k]!=0 &&a[j]!=0)
{
if(a[k]%a[j]==0)
a[k]=0;
}
}
for(int m=0;m<=100;m++)
if(a[m]!=0)
cout<<a[m]<<" ";
return 0;
}
·
上一篇: 2021-02-16
下一篇: 素数的一般判断方式 3+1种