• 2007-11-22

    [Code]对素数检测法的一点点点点改进 - [Code]

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

           话说今晚我很崩溃地得知,我的哲学选修课也要写论文了……      

           2008.5.20,关于以下冗长兼SB的证明,有邹伟大神指出,一切都只不过一句话:M=(2K+1)=(2k+1)(2m+1),即奇合数总可分解成两奇数之积……

    ===============================================

        检测一个大于2的数M(非超级素数之类的,只是任意一个平常数)是否为素数,我们所熟知的传统方法是:在[3sqrt(M) ]的范围内逐一检测各奇数是否为M的因数,若检测全部通过,则M为素数。

           今天在想一道题时无意发现了一个可以对此稍作优化的方法,虽然没有根本上的数量级优化,但至少对于M较大时可以作为一点点小小的改进。

           方法如下(随证明而说明):

           step1:任意一大于2的数M,只有在其非偶时才可能为素数,故需要判断的M一定可表达成2K+1的形式。

           step2:此时的M如果为合数(非素),则其必有一奇数因子,假设此因子为2k+1

           step3:设n为任意正整数,当M通过(2K+1/2k+1= n的检测时,即可证明M为非素数。反之,当所有可能的k值取遍后检测仍未有通过,则M为素数。

           step4:(由于我找到此方法的灵感比较特殊,故而下面的证明也很“特殊”,大家忍耐一下,哈……)

           现在,将step3式子中的数字“1和“2分成看成两个非数字量,即你可以拿一个符号什么的暂时代替,以下我的书写中将用乘号*特别体现这一点。

           step3的判断式进行变换可以得到:1+2*K = 1*n + 2*n*k

           得:1*(n-1) + 2( n*k - K ) = 0   设一任意正整数m,并将上式转换成一个方程组,

           即:(1)n – 1 = 2m (2) K - n*k = m

           (1)代入(2)中,消去n,最终得 K – k/2k + 1 = m

    step5step4中已经将原来的判断式化成另一个判断式了,这个判断式中要进行变量的是k,而k的取值范围根据 3 <= 2k+1 <= sqrt2K+1 求得 k属于[ 1 ( sqrt1+2K- 1)/2 ]

     

           好拉,稍微优化的方法就是以这最终这条式子和一个取值范围进行操作。具体实现的大概代码如下(上面出现过的变量不再定义):

           int odd = 3, m = ( sqrt1+2K- 1)/2;

           bool prime = true;

           for ( K--, k = 1; k<m+1 ; k++, K--, odd+=2)

           {      if ( K % odd == 0)

                  {

                         prime = false;

                         break;

                  }

           }

     

           这里的所谓优化就在于,判断式的计算的是K而非M,初始值小了一半,然后每次判断前都会有递减,有兴趣的拿去用用看看有没有帮助。看完这么废的方法的冗长说明,你终于明白被我耍了吧?哈哈哈哈……

    分享到:

    历史上的今天:

    评论

  • 喂 5是27号咩
    5复我短信
  • 举例说明嘛..看到一堆变量就头疼....


    附:人家写的...线性时间的筛选出1--N间的素数...

    发信人: wanglei (wanglei), 信区: ACMICPC
    标 题: [转载]素数的线性筛法
    发信站: 逸仙时空 Yat-sen Channel (Thu Oct 25 10:25:50 2007)

    发信人: xreborner (xreborner), 信区: Algorithm
    标 题: Re: cuiaoxiang申请Algorithm版版主
    发信站: 日月光华 (2007年10月10日12:52:28 星期三), 站内信件

    vector<bool> P(N + 1, true);
    vector<int> Primes;
    int Time = 0;
    for (int I = 2; I <= N; I++)
    {
    if (P[I])
    {
    Primes.push_back(I);
    Time++;
    }
    for (int J = 0; J < (int)Primes.size() && I * Primes[J] <= N; J++)
    {
    P[I * Primes[J]] = false;
    Time++;
    if (I % Primes[J] == 0) break;
    }
    }
    cout << Time << " " << Primes.size() << endl;
    --
    回复小龙女说:
    呵呵那是最经典的筛法,是求一个范围内的所有素数的(而我的确也是在做一道可以用筛法解决的题目时不小心想到了自己写的方法),而我现在想做的是判断一个数是否为素数的问题,只是一个数。
    我的方法用的当然也是线性时间,而且线性系数要小于筛法,而筛法之所以不作为解决判断一个范围不定数是否为素数的理想方法,是因为筛法会对空间有很多消耗。

    汗,要举例啊,只要自己选一个正整数K代进去就可以明白了……方法的正确性应当是没错的,我做题时已经用此法通过了。
    另:刚刚发现实现代码里的循环语句不完整,估计是复制粘贴时的问题,已经补充上了。
    2007-11-23 23:40:36
  • 发现你最近写的东西都好高深,看不懂中...
    唉~真的是阔别数学好久了,倒也明白“天书”的含义了...
    真的是隔行如隔山啊...
    默.......
    回复珊痕说:
    不要这么说,要知道我看你的德文也是看天书啊……哈,隔行的确是这样的,不过共同的东西总是有的,所以上次看到你BLOG上的中秋赋词才觉得那么高兴,因为这些都是共同喜爱的东西。

    可其实呢,我写的都是些在这个专业里很简单的东西,我去很多高手的BLOG看都是看不懂的,这个比你去一个德文BLOG看可能更郁闷……

    不要默噢,我的生活真的被太多东西填满了,很多朋友的BLOG都被我冷落了,唉……说实在的,你能来看一看我已经很高兴了,呵呵。
    2007-11-23 23:53:47