java - 朴素素数测试优化

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

如果您想坚持使用原始方法，那么下一步就是使用您链接到的维基百科页面中列出的下一个属性:

So all prime numbers are of the form 30k + i for i = 1, 7, 11, 13, 17, 19, 23, 29 (i.e. for i < 30 such that gcd(i,30) = 1).

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

您可以将 6 步循环替换为 30 步循环，(并手动检查所有小于 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%。当您向列表中添加更多素数时，您会得到递减的返回。

实际上，如果您需要快速素数检查，那么您需要摆脱朴素的方法。之前有很多关于堆栈溢出的问题。