特定の疑似コードで書くと、あなたの意図は
pe3 = last [x | x <- [2 .. 775146], isPrime x, rem 600851475143 x == 0]
それを読んでください: 2 から 775146 までの範囲で描画された場合、保持されている場合、0 の場合、そのようなものを収集します。最大のものを返しxisPrime x600851475143 % xxます。(g x)また、ここでは括弧なしでアプリケーションを単にg x.
剰余の計算は、素数性のテストよりもコストがかからないため、2 つの操作を入れ替えます。
pe3 n = last [x | x <- [2 .. isqrt n], rem n x == 0, isPrime x]
このアルゴリズムは関連する特定の数値に対して機能する可能性がありますが、残念ながら一般的には正しくありません。たとえば、整数の平方根が 3000 である 9000009 の場合、101 が返されます。しかし、9901が正しい答えです (つまり、9901 は 9000009 の最大の素因数です)。 、101 ではありません)。
代わりに、最初に最小の素因数を見つけることに焦点を当てましょう。
pe3a n = head ([x | x <- [2 .. isqrt n], rem n x == 0, isPrime x] ++ [n])
なぜ( ... ++ [n])(++リストの連結を意味する)?? それn自体が素数の場合、除数はまったく見つからず、最初のリストは空に戻るため、[]. その場合、答えはnそれ自体でなければなりません。headしかし、そうでない場合、答えは除数リストの最初 (つまり) になります。もちろん、それを見つけたら、それ以上探し続ける必要はありません。最小のものだけが必要な場合は、1 つだけで十分です。
OK、それで (架空の遅延疑似コード インタープリターで) 試してみると、最初の因数として 3 が得られます。
> pe3a 9000009
3
これで、その 3 を数から割ることができます。
> div 9000009 3
3000003
そして、9000009 の代わりに 3000003 で続行します。つまり、3000 ではなく、平方根 1732 で停止できるということです。効率が大幅に向上します。また、2 からやり直す必要はありません - 既にテストされています - 最後に見つかった要素から始めることができます:
pe3b (start, n) = (d, div n d)
where
d = head ([x | x <- [start .. isqrt n], rem n x == 0, isPrime x] ++ [n])
> pe3b (3, 3000003)
(3,1000001)
そのため、2 番目の 3 が返され、その数が見つかった除数で再び除算されます。
> pe3b (3, 1000001)
(101,9901)
次に見つかった素因数は 101 で、ここで因数分解する数は 1000001 / 101 = 9901 です。ここでも、最後に見つかった除数 101 から始めます。これは、小さい方の除数はすべて既に試されているためです。
> pe3b (101, 9901)
(9901,1)
面白い。isqrt(9901) == 99、リスト[101 .. 99]は空であるため、結果はすぐに生成されました。9901 はそれ自体が 100 を超える最初の因数であり、実際には 1 を超えています。これまでのすべての数は、すでに連続して試行され、分割されているためです。つまり、9901 は素数であり、素数性をテストする必要はありません。
実際、このアルゴリズムによって検出されたすべての要素は、同じ推論によって構成によって素数であることが保証されてisPrimeおり、すべての呼び出しは不必要でした。
また、ここで除算 (剰余演算) が実行された最大数は、3000 ではなく 101 であることに注意してください。新しいアルゴリズムは正しいだけでなく、はるかに効率的です!
これで、Scheme でこのアルゴリズムを繰り返しpe3b適用し、最後に見つかった係数で割ることができます。1になったらストップ。
したがって、同じ擬似コードで、
divStep (start, n) = (d, div n d)
where d = head ([x | x <- [start .. isqrt n], rem n x == 0] ++ [n])
pe3 n = fst . until ((== 1) . snd) divStep $ (2,n) -- (1st,2nd) in a tuple
factorizing n = takeWhile ((> 1) . fst) . drop 1 . iterate divStep $ (2,n)
factors n = map fst . factorizing $ n
isPrime n = factors n == [n]
「の」.と読みます。pred step startは、述語が満たされるまで (結果の 2 番目のコンポーネントが 1 になることを意味します)、関数を繰り返し適用する高次パターンです。通常、named を使用して Scheme でコーディングされます。$until ((== 1) . snd)let
計算の全履歴を見るために、iterate step startはすべての中間結果を収集する別のパターンです (そして開始値は必要ないので、それを取得しますdrop)。因子自体だけを見るために、各結果の最初の成分を で取得しmap fstます。それ自体が 1 より大きい唯一の約数である場合、その数値は素数です。テスト:
> pe3 9000009
9901
> factorizing 9000009
[(3,3000003),(3,1000001),(101,9901),(9901,1)]
> factors 9000009
[3,3,101,9901]
> pe3 600851475143
6857
> factorizing 600851475143
[(71,8462696833),(839,10086647),(1471,6857),(6857,1)] -- 1471 is the largest
> factors 600851475143 -- factor tried,
[71,839,1471,6857] -- *not* 775146 !!
> factors 600851475143999917 -- isqrt 600851475143999917 == 775146099
[41,37309,392798360393] -- isqrt 392798360393 == 626736