Chinaunix首页 | 论坛 | 博客
  • 博客访问: 591103
  • 博文数量: 92
  • 博客积分: 5026
  • 博客等级: 大校
  • 技术积分: 1321
  • 用 户 组: 普通用户
  • 注册时间: 2008-02-28 11:04
文章分类

全部博文(92)

文章存档

2011年(9)

2010年(17)

2009年(12)

2008年(54)

我的朋友

分类: C/C++

2009-04-22 22:27:13

所谓“筛选法”指的是“埃拉托色尼(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 <stdlib.h>
#include <math.h>


int main() {

        int num = 100;

        int a[101];

        for(int i=0; i<=101; i++) {
                a[i] = i;
        }
        a[1] = 0;

        for (int i=2; i<sqrt(num); i++) {
                for (int j=i+1; j<=num; j++) {
                        if (a[j]!=0 && a[j]%i==0) {
                                a[j] = 0;
                        }
                }
        }

        for(int i=1, n=0; i<=100; i++) {
                if (a[i] != 0) {
                        printf("%d\t", a[i]);
                        if(++n%10 == 0) {
                                printf("\n");
                        }
                }
        }

        printf("\n");

        return 0;
}

阅读(18614) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~