与えられた数の約数を計算するための最も最適なアルゴリズム（パフォーマンスの面で）は何でしょうか?
疑似コードや例へのリンクを提供していただければ幸いです。
編集: すべての回答がとても役に立ちました。ありがとうございます。私はアトキンの篩を実装し、その後、Jonathan Leffler が示したものに似たものを使用するつもりです。Justin Bozonier が投稿したリンクには、私が求めていたものに関する詳細情報が記載されています。
ベストアンサー1
Dmitriy の言うとおり、素数リストを生成するにはアトキンのふるいが必要ですが、それで問題全体が解決するとは思えません。素数リストができたので、そのうちのいくつの素数が約数として機能するか (そして、その頻度) を確認する必要があります。
アルゴリズム用のPythonはこちら
ここを見て「件名: 数学 - 除数アルゴリズムが必要」を検索します。ただし、リスト内の項目を返すのではなく、項目の数をカウントするだけです。
数学博士です数学的に何をする必要があるかを正確に説明します。
本質的には、数が次の場合になりますn:
n = a^x * b^y * c^z
(ここで、a、b、c は n の素約数、x、y、z は、その約数が繰り返される回数)、すべての約数の合計は次のようになります:
(x + 1) * (y + 1) * (z + 1)。
編集: ところで、a、b、c などを見つけるには、私が正しく理解していれば、貪欲なアルゴリズムを実行する必要があります。最大の素数から始めて、さらに乗算すると数値 n を超えるまで、それを自身で乗算します。次に、次に小さい因数に移動し、前の素数 ^ 現在の素数で乗算した回数を乗算し、次の数が n を超えるまで素数で乗算し続けます... など。約数を乗算した回数を記録し、それらの数値を上記の式に適用します。
私のアルゴリズムの説明については 100% 確信はありませんが、それがそうでない場合は似たようなものになります。