• 筛选法求素数 - [学习]

    2008-08-28

    Tag:

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/chaoyueziwo21-logs/28273435.html

    谓“筛选法”指的是“埃拉托色尼(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   29
    31   37   41   43   47   53   59   61   67   71
    73   79   83   89   97
    =================================================

    分享到: