1

我正在学习试验划分素数测试的基础知识，因此，在代码中实现它。可以使用许多技巧来提高算法的性能，例如：

1) 仅将试验除法运行到平方根 (n)

2）通过创建一个直到平方根（n）的筛子来用内存换取时间，然后只在创建的筛子中的素数上运行试除法

n%6但是，如果发现 (n mod 6)的值1 or 5（使用 6k +/- 1 规则），我没有找到将结果作为复合返回的想法。在我们的素数确定测试中使用这个规则不会提高它的性能吗？如果是，为什么没有在任何地方提到它？如果不是，为什么会这样？

谢谢。

4

4 回答 4

3

看起来你属于初级水平以上的人（那些永远不会想出这个想法的人），低于那些寻求极端表现的人。所以这个想法对于初学者来说有点难以解释，对于非常高级的人来说似乎微不足道。

它将运行时间减少了三分之一，或者让您同时测试 50% 以上的数字。你可以通过做更少的除数不太大的测试来节省更多：假设你测试一个大约十亿的数字。你有一个循环，除数 d = 6k-1，你想测试 d 和 d+2 = 6k+1。所以你只测试 d^2 ≤ p，你不测试 (d+2)^2 ≤ p。最坏的情况是，你测试的除数比你需要的多。最好的情况是，您可以节省几千个 (d+2)^2 ≤ p 的测试。

通过观察唯一可能的 ≥ 30 的素数是 30k + 1、7、11、13、17、19、23、29，您可以节省更多，避免使用 30k + 5 和 30k + 25。

于 2016-06-26T13:24:03.670 回答
1

这里的通用方法称为Wheel Factorization。最简单的轮子是对 2 进行特殊处理，然后只测试奇数：2 轮子。下一个最简单的是您在问题中提到的 2,3 轮。@gnasher729 给出了上面 2、3、5 轮的数字。

您可以通过从 5 开始交替添加 2 和 4 来生成 2,3 轮的数字。

伪代码：

boolean isPrime(num)

  // Deal with factor 2.
  if (num MOD 2 = 0) then
    return (num = 2)
  endif

  // Deal with factor 3.      
  if (num MOD 3 = 0) then
    return (num = 3)
  endif

  // Factors >= 5.
  limit <-- 1 + sqrt(num)
  trialFactor <-- 5
  step <-- 2
  while (trialFactor < limit) do
    if (num MOD trialFactor = 0)
      // Number not prime
      return false
    endif
    trialFactor <-- trialFactor + step
    step <-- 6 - step
  endwhile

  // Number is prime here.
  return true

end

这比 Sieve 使用更少的内存，但对于非常大的素数来说太慢了。

于 2016-06-26T14:41:31.517 回答
1

您对测试的想法n % 6完全等同于测试n % 2，n % 3因此如果您将后者作为普通试验部门的一部分进行，那么进行前者是多余的。

正如@gnasher729 在他们的优秀答案中所解释的那样，一个密切相关的想法是（在考虑了 2 和 3 之后）只查看形式的试除数 , 6k+1。6k-1

于 2016-06-26T13:27:05.033 回答
1

这个技巧的工作方式：制作一堆小素数的 M 的乘积。然后，当测试一个数 N 时，如果 (N%M) 为 0 或与 M 有一个共同因子，您可以立即说 N 是合数。

您使用了 6，即 2 和 3 的乘积。在可能的模数 0、1、2、3、4、5 中，只有 1 和 5 没有因子 2 或 3。

不过，6 并没有什么特别之处——你可以用任何模数做同样的技巧，尽管你想让它成为小素数的乘积，以最大化复合模数的密度。

请注意，在进行此检查后（如 gnasher 所示），您只需要测试与 M 没有共同因子的试除数。

于 2016-06-26T13:27:09.110 回答