欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(谭c++5.1)筛选法求100之内的素数

程序员文章站 2022-03-13 12:21:17
...

筛选法指的是“埃拉托色尼(Eratosthenes)筛选法”。他是古希腊著名数学家。他采取的方法是:在一张纸上写上1~1000全部整数,然后逐个判断他们是否为素数,找出一个非素数就把他挖掉。最后剩下的就是素数。

具体做法:

  1. 先将1挖掉
  2. 用2去除它后面的个数,把能被2整除的数挖掉,即挖掉2的倍数
  3. 用3去除他后面的各个数,挖掉3的倍数
  4. 分别用4、5......各数作为除数去除这些数以后的各个数。这个过程一直进行到在除数后面的数已全部被挖掉为止。(事实上,可以简化,如果需要找1~n范围内的素数表,只需进行到除数为sqrt(n)取其整数)

上面的算法可以表示为:

  1. 挖去1
  2. 用下一个未被挖去的数p去除p后面各数,挖掉p的倍数
  3. 检查p是否小于根号n的整数部分,如果是,则返回2继续执行,否则就结束
  4. 纸上剩下的数就是素数
#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;
}


·

相关标签: 素数