《C程序设计第二版》(谭浩强) 关于素数的判定，参见： [031] 判断m是否是素数。 所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。他是古希腊的著名数学家。他采取的方法是，在一张纸上写上1到100全部整数，然后逐个判断它们是否是素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。 具体做法如下：<1> 先将1挖掉(因为1不是素数)。<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。<3> 用3去除它后面的各数，把3的倍数挖掉。<4> 分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如找1～50的素数，要一直进行到除数为47为止（事实上，可以简化，如果需要找1～n范围内素数表，只需进行到除数为n^2(根号n)，取其整数即可。例如对1～50，只需进行到将50^2作为除数即可。） 如上算法可表示为：<1> 挖去1;<2> 用刚才被挖去的数的下一个数p去除p后面各数，把p的倍数挖掉;<3> 检查p是否小于n^2的整数部分（如果n=1000, 则检查p<31?），如果是，则返回(2)继续执行，否则就结束;<4> 纸上剩下的数就是素数。 #include <stdio.h>#include <math.h> int main(void){    int i;    int j;    int a[101];                // 为直观表示，各元素与下标对应，0号元素不用     for (i = 1; i <= 100; i++) // 数组各元素赋值        a[i] = i;     for (i = 2; i < sqrt(100); i++)     // 外循环使i作为除数        for (j = i + 1; j <= 100; j++)  // 内循环检测除数i之后的数是否为i的倍数        {            if (a[i] != 0 && a[j] != 0) // 排除0值元素                if (a[j] % a[i] == 0)                    a[j] = 0;           // i后数若为i的倍数，刚将其置0(挖去)        }     int n = 0;    // 对输出素数计数, 以控制换行显示     for (i = 2; i <= 100; i++)    // 输出素数    {        if (a[i] != 0)        {            printf("%-5d", a[i]); // 输出数组中非0元素(未挖去的数)            n++;        }        if (n == 10)        {            printf("\n");         // 每行10个输出            n = 0;        }    }    printf("\n");     return 0;} 运行结果(VC):=================================================2    3    5    7    11   13   17   19   23   2931   37   41   43   47   53   59   61   67   7173   79   83   89   97=================================================

评论