/*
写出不超过100的所有的素数。
解  将不超过100的正整数排列如下：

 1   2   3   4   5   6   7   8   9  10
11  12  13  14  15  16  17  18  19  20
21  22  23  24  25  26  27  28  29  30
31  32  33  34  35  36  37  38  39  40
41  42  43  44  45  46  47  48  49  50
51  52  53  54  55  56  57  58  59  60
61  62  63  64  65  66  67  68  69  70
71  72  73  74  75  76  77  78  79  80
81  82  83  84  85  86  87  88  89  90
91  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;
}

评论