朴素素性测试优化

Question

我有一个用来测试素性的算法，它使用如下所示的朴素实现http://en.wikipedia.org/wiki/Primality_test#Naive_methods

       static boolean check(int n)
   {
           if(n == 2 || n == 3)
           {
                   return true;
           }
           if(n < 2 || n % 2 == 0 || n % 3 == 0)
           {
                   return false;
           }
           for(int i = 6; i * i <= n; i += 6)
           {
                   if(n % (i - 1) == 0 || n % (i + 1) == 0)
                   {
                           return false;
                   }
           }
           return true;
   }

我一直走到6k+1区，但在那之后，我就迷路了。除此之外，我还能如何进一步优化速度呢？

Answer 1

如果您想坚持使用naive方法，那么下一步就是使用您链接到的wikipedia页面中列出的下一个属性：

因此，当i= 1，7，11，13，17，19，23，29时，所有质数都是30k +i的形式(即对于i< 30，使得

(i，30)= 1)。

除了您可能会选择与2.3.5略有不同/更多的素数

您可以用30步循环替换6步循环(并手动检查所有小于30的素数)

代码可能如下所示：

    static boolean check(int n)
   {
           if(n<30)
           {
              return n==2 || n==3 || n==5 || n==7 || ...
           }

           for(int i = 30; i * i <= n; i += 30)
           {
              if (n % (i + 1))==0 return false;
              if (n % (i + 7))==0 return false;
              if (n % (i + 11))==0 return false;
              if (n % (i + 13))==0 return false;
              if (n % (i + 17))==0 return false;
              if (n % (i + 19))==0 return false;
              if (n % (i + 23))==0 return false;
              if (n % (i + 29))==0 return false;
           }
           return true;
   }

但是您会注意到，这个循环扫描8/30 (=27%)数字，而6步进循环扫描2/6 (=33%)，所以它扫描的数字减少了大约20%，所以您预计速度最多会提高20%。当你将更多的素数添加到列表中时，你会得到递减的回报。

真的，如果你需要快速质数检查，那么你需要远离幼稚的方法。之前有很多关于堆栈溢出的问题。