我怎样才能加快素性检查器的速度？

Question

我有一个函数 FIsPrime，它接受 int64 和 returns 布尔值 True 或 False，具体取决于给定的 int64 是否为质数。

function FIsPrime(P:int64):boolean;

  var
  I:int64;
  RSqrtP:Extended;

  begin
    I:= 3;
    RSqrtP := sqrt(P) + 1;

    while ((P mod I) <> 0) AND (I <= RSqrtP) AND ((P mod 2) <> 0) do
      I := I + 2;

    if I < RSqrtP then
      FIsPrime := False
    else
      FIsPrime := True;
  end;

然而，虽然这有效，但速度很慢。检查从 10⁶ 到 5×10⁶ 的数字需要 4 秒。

我正在测试 10¹² 和 10¹⁵ 顺序的数字 - 整个代码选择一个随机数并将其×通过 10¹² 得到一个大的随机数。

这个随机数是运行通过FIsPrime函数加1直到它是素数：

function FFirstPrimeAbove(P:int64):int64;

  var
    BIsPrime: boolean;

  begin
    if P mod 2 = 0 then
      inc(P);

    repeat
      BIsPrime := FIsPrime(P);
      P := P + 2;
    until (BIsPrime);

    FFirstPrimeAbove := P;
  end;

这可能需要一段时间 - 10¹² 大约需要 6 秒，10¹⁵.

大约需要 7 秒

虽然 14 秒不多，但很烦人。有没有办法用更高效的算法来减少这个时间？

我是 Pascal 的新手，但我已经编程多年了 - 所以任何更高效的算法都会有用。

我看了 AKS Test 但有很多行话需要克服 - "polynomial congruence relation"、"generalization to polynomials" 和 "binomial coefficient" 挑几个。

任何关于我如何在 Delphi 中实现某些东西的基本提示将不胜感激。

Answer 1

我怀疑提高速度最有效的简单方法是创建一个 table 个已知素数。

可能有太多素数，无法存储所有适合 64 位整数的素数。但是您可以存储小于 sqrt(high(int64)) 的所有素数。然后，当您循环抛出可能的除数时，您只能检查素数。这应该会带来非常显着的好处。

所以，算法大纲是：

用小于sqrt(high(int64))的所有素数填充一个数组。这应该是预先计算好的。
要测试一个值 N 是否为质数，首先找到它的根，sqrt(N)。
然后尝试将质数除以被测值，直到得到大于sqrt(N)的质数。
如果你走到那一步，N 就是质数。否则，如果你找到一个质因数，它就不是质数。

Answer 2

将 RSqrtP 更改为 Int64 很可能会提高性能。我没有测试它，但我希望比较 float 值和 int64 值不是最快的。

让 ((P mod 2) <> 0) 脱离循环。

另外，如果您不介意您的应用程序有更长的初始化时间，您可以加载 2 和 X 之间所有素数的列表，并在进入 I+2 例程之前从它们开始。你不需要尝试除以非素数，因为这已经被素数处理了（即任何可以被 4 整除的都将被 2 除，任何可以被 49 整除的也将被除以7 等)

我不久前发布了 an article 关于使用质数作为示例进行优化的信息。也许您会在那里看到更多可以帮助您的信息。

我怎样才能加快素性检查器的速度？

How can I speed up a primality checker?

delphi

performance

primes

pascal