• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-09-04)  算法/数据结构 |   20 条评论  11 
    文章评分 0 次,平均分 0.0

    1. 筛法求素数(只能被1和自身整除的正整数是素数)。
    用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。如有:
    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
    1不是素数,去掉。剩下的数中2最小,是素数,去掉2的倍数,余下的数是:
    3 5 7 9 11 13 15 17 19 21 23 25 27 29
    剩下的数中3最小,是素数,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为:
    2 3 5 7 11 13 17 19 23 29
    写程序时,采用一个数组,用数组的下标表示自然数,如果一个数不在筛中就将其对应的元素值赋0,如果仍在筛中,则那个元素值为1.

    36d6a74bd11373f0c2bbe702a50f4bfbfaed0438.jpg

    #include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<cmath>
    #include<time.h>
    using namespace std;
    bool key[2010];//true表示是素数
    int main()
    {
             int n;
             while(scanf("%d",&n)&&n)
             {
                       for(int i=2;i<=sqrt(n+0.0001);i++)
                       {
                                if(!key[i]){
                                         if(i<sqrt(n+0.0001)/i)
                                              for(int j=i*i;j<=n;j+=i)key[j]=true;
                                 }
                       }
                       key[1]=true;
                       for(int i=1;i<=n;i++)
                                if(!key[i])printf("%d ",i);
                       printf("\n");
             }
    }   
     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/1996.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享