/*写出不超过100的所有的素数。解  将不超过100的正整数排列如下： 1   2   3   4   5   6   7   8   9  1011  12  13  14  15  16  17  18  19  2021  22  23  24  25  26  27  28  29  3031  32  33  34  35  36  37  38  39  4041  42  43  44  45  46  47  48  49  5051  52  53  54  55  56  57  58  59  6061  62  63  64  65  66  67  68  69  7071  72  73  74  75  76  77  78  79  8081  82  83  84  85  86  87  88  89  9091  92  93  94  95  96  97  98  99  100按以下步骤进行：(ⅰ)  删去1，剩下的后面的第一个数是2，2是素数；(ⅱ)  删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；(ⅲ)  再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；(ⅳ)  再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；  L L照以上步骤可以依次得到素数2, 3, 5, 7, 11, L。由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。*///Eratosthenes筛法求1-100之间的素数#include <cstdlib>#include <iostream>#include <cmath>using namespace std;bool judge(int n)//判断该n是否为素数{    bool j=1;    for (int i=2;i<sqrt(n);i++)    {        if (n%i==0)        {            j=0;        }    }    return j;}void del(int n,int *a)//删去n后面的被2整除的数{    for (int i=n;i<100;i++)    {        if(a[i]%n==0)            a[i]=-1;    }}int main(int argc, char *argv[]){    int a[100];    for(int i=0;i<100;i++)        a[i]=i+1;    a[0]=-1;    for (i=2;i<sqrt(100);i++)//任何大于1的合数a必有一个不超过 的素约数    {        if(judge(a[i]))        {            del(i,a);//如果为素数,将该数设置为-1        }    }        for(i=0;i<100;i++)//输出    {        if(a[i]>0)        cout<<a[i]<<" ";    }    system("PAUSE");    return EXIT_SUCCESS;}

评论