1

私は試行分割の素数性テストの基本を行っていたので、それをコードに実装しました。アルゴリズムのパフォーマンスは、次のような多くのトリックを使用して向上させることができます。

1) 平方根 (n) までの試行分割のみを実行する

2) 平方根 (n) までのふるいを作成し、作成したふるいの素数に対してのみ試行除算を実行することにより、メモリを時間と交換します。

しかし、(n mod 6) の値が ( 6k +/- 1 ルールを使用しn%6て) 判明した場合、結果を複合として返すという考えはどこにもありませんでした。1 or 5素数決定テストでこのルールを使用すると、パフォーマンスが向上しませんか? はいの場合、なぜそれがどこにも言及されていないのですか? いいえの場合、なぜそうなるのですか?

ありがとう。

4

4 に答える 4

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 に答える