ウィキペディアのページで指定されている基本的なアルゴリズムに従って、Haskell に 2 次ふるいを実装しました。ほとんどの整数でうまく機能しますが、n乗である数値Nの因数分解を見つけることができません。偶数乗 (平方) の場合、アルゴリズムはループし、奇数乗の場合、N を法とする平方であるいくつかの滑らかな数を見つけます (私はこれをテストして確認しました)。些細な要因。
ウィキペディアのアルゴリズムを文字どおりに実装したことは十分に確信しています。n乗を処理できないバージョンのアルゴリズムに問題がありますか、それとも私のアルゴリズムにバグがありますか?
なんらかの理由で、 stackoverflowでコードのフォーマットに問題が発生しています。
私が理解しているように、二次ふるいは、数値を確実に因数分解するようには設計されていません。むしろ、典型的なケースでは、通常、数を因数分解するように設計されています。
たとえば、ウィキペディアのエントリは、少なくとも今日の時点では、「対数最適化または素数ベキを使用しない標準的な二次ふるい」として提示されるものを説明しています。したがって、明示的に素数ベキは考慮されません。
さらに、私が理解しているように、素数べき乗に近い数の因数分解も、アルゴリズムのより効率的なバリエーションではうまく機能しません。
したがって、障害はコードにあるのではなく、アルゴリズムが通常提示される方法にあります(常に機能するか、通常は機能するかなどの問題について詳しく説明します:-))