签到

11月01日
尚未签到

共有回帖数 0 个

    霜晨守候

    等级：
    素数，亦称质数，指在一个大於1的自然数中，除了1和此整数自身外，无法被其他自然数整除的 数。换句话说，只有两个正因数（1和 自己）的自然数即为素数。
    素数这个概念 , 这个估计大家都不陌生 , 因为小学就已经接触了.
    此贴将会讨论一个很经典的素数问题.在 0~N 的自然数范围中 , 数出在此范围之内的素数个数.为了方便 , 也同是也是数学定义 , 我们称之为 π(n)
    π(10) = 4因为 10 之内的素数只有4个 -- 2 , 3 ,5 ,7
    关於π(n) 问题 , 最主流的方法也就是2种 , 也是小学的时候都学会的方法

    1 ) 从 2`n 逐个验证 , 若是检验到某数是素数的时候 , 则+1

    2 ) 打表法 , 也是所谓的埃拉托斯特尼筛法

    1 , 2 法随便找本c语言的书籍就有写了

    以耗损时间的角度来说(不是时间复杂度,此类问题的时间复杂度不可以用多项式表达)
    方法1最耗时

    以空间复杂度来说 , 第1种方法的空间复杂度是O(1), 只需消耗一个空间即可
    第2种方法的空间复杂度是O(n) ,

    -------------------

    接下来还有一个很不常用的方法

    消耗时间比1) 2) 方法来的更少
    且 空间复杂度只有 O(sqrt(n))

    那就是勒让德法则 , 当然还有更先进的Ernst Meissel法则, 还有黎曼ζ函数
    但是勒让德法则算是以上法则当中最容易了解

    所需的数学知识有 - 离散数学 , set论 , 斥容定理等

    本贴不详细的证明此法则.
    在成功写出以下程序之前 , 我大概失败了4次 , 共花费48小时来写 .第1次压堆 ,发现根本没那麼多记忆体可压 , 於是最后的那几次则是用到递归概念 , 然后优化 , 节枝 等等. 每次的失败给之后的优化带来不少灵感 .
    大家可以看出那个Recusion中有不少retrun , 那是为了节枝而定的

    #include ctime
    #include cstdio
    #include cstdlib
    bool primeTable[32000];int prime[3410];
    int p ,q , r = 1000000000 , s ;
    int stack[9];int ctrl = 0;
    long long result = r-1;

    void findPrime()
    {
       for(int i=2;i32000;primeTable[i++]=true);
       for(int i=2;i=177;i++)
           for(int j=i+i;j32000;j+=i)primeTable[j] = false;
       for (int i=2;i32000;i++)
           if ( primeTable && i  31622 )
               prime[p++] = i;
    }

    void Recusion(int start,int size,int N,long long pre)
    {
       if ( size == q )
       {
           result += N*r/pre;
           return;
       }
       if ( (bool)(ctrl) )
       {
           --ctrl ; return;
       }
       for (int i = start ;i  p ; i++)
       {
           long long temp = 1;
           temp = pre * prime;
           if ( temp  r )
           {
               for(int i= size ; i;i--)
                   if ( stack - stack[i-1] == 1 )
                       ctrl++;
                   else break;
               return ;
           }
           stack[size] = i;
           Recusion(i+1,size+1,N,temp);
       }
    }

    int main()
    {
       clock_t start = clock();
       findPrime();
       for (q = 1,s = -1;q=9;q++,s*=(-1))
           Recusion(0,0,s,1);
       result += p;
       clock_t end = clock()-start;
       printf("0~1,000,000,000 , having %d prime numbersn",result);
       printf("It used %d msn",(int)end);
       system("pause");
    }

    以上是 π(1000000000) 的程序

    在我的 2G物理内存 , Inter Pantinum Dual E2160 1.80GHz 1.79GHz 处理器
    作业平台 xp professional service pack 2 繁体中文版上运行
    花费时间 24000 毫秒 (24s左右) , 记忆体  1M
    结果 π(1000000000) = 50,847,534

    通过此又让我想起另外一个问题 , 那就是排序

    若是只要我排序2个数字 , 那麼 , 我值要找出哪个大哪个小就可以了
    若是只要我排序10个数字 , 仍然可以找出那10个数中最大的数字 , 然后抽出 , 往下解决剩余9个数中最大的数字是那个 (这也是插入排序法的原理)
    若是只要我排序100个 , 我会用冒泡排序法
    若是排10000个 , 那麼会用比冒泡 插入 排序法更复杂的 快速排序法 , 或是合并排序法
    但是 当要我排1百万个的时候 , 原先的快速排序法变会失效 , 因为可能内存不足 , 这时候便需要借住外部文件帮助 -- 外部排序法

    显然对於一个排序问题 , 虽然排100万个跟排1万个的原理是一样
    但是在实现的过程中变很显然不同
    前者的复杂度要比后者的要高出指数倍 而不是100倍

    说回那个素数问题
    若是 π(n) , n = 1,000 的话 , 那麼方法 1 , 2 都能走的通
    若是 1,000  n = 1,000,000 , 方法1显然就不行了 , 不过可以通过打表解决
    若是 1,000,000  n = 10,000,000 , 仍然可以打表 , 不过不能打全表 ,途中需要优化
    若是 n  100,000,000 的话 打表法已经无用了 , 那只能另循新路了

    关於此问题 , 其实还有一个 O(1)空间复杂度 , O(1)时间复杂的算法
    可以求出 π(n)的大概值
    那就是素数定理
    π(n) =n/In(n)
    只能求出大致的值 ,让求精确值之前让心理有个度, 此定理在18xx年由某法国数学家证明出来
    其中 ln 是自然对数

    今天又成功优化

    使得[0,1000万] 只需要 62毫秒
    [0,1亿] 只需要 640毫秒
    [0,10亿] 只需要 6300毫秒

    比起之前
    [0,1亿] 只需要 2000毫秒
    [0,10亿] 只需要 24000毫秒 快了很多

    记忆体消耗也比之前少了

    楼主 2015-11-05 13:10 回复

共有回帖数 0 个
  • 回 帖
  • 表情 图片 视频
  • 发表

登录直线网账号

Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号 意见反馈 | 关于直线 | 版权声明 | 会员须知