1. ホーム
  2. performance

[解決済み] 与えられた数の除数の数を計算するアルゴリズム

2022-04-20 12:26:16

質問

与えられた数の約数を計算するために、最も最適なアルゴリズム(パフォーマンス的に)は何だろう?

疑似コードやサンプルへのリンクを提供していただけると幸いです。

EDIT: すべての回答がとても役に立ちました、ありがとうございます。AtkinのSieveを実装し、その後Jonathan Lefflerが示したものと似たようなものを使おうと思っています。Justin Bozonierが投稿したリンクには、私が欲しかったものについての更なる情報があります。

どのように解決するのか?

Dmitriyの言う通り、素数リストを生成するためにアトキンのふるいが必要ですが、それですべての問題が解決するとは思えません。素数のリストができたので、これらの素数のうちいくつが約数として作用するか(そしてその頻度)を確認する必要があります。

<ストライク アルゴのためのPythonは以下の通りです。 ここを見る で検索し、「"Subject: math - need divisors algorithm"」で検索してください。ただし、リスト内のアイテム数を返すのではなく、カウントするだけです。

ここに数学博士がいる では、数学的に何をする必要があるのかを説明しています。

要するに、もしあなたの数字が 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を超えるまで素数を掛け続ける...などです。除数を掛け合わせた回数を記録しておき、それらの数字を上の式に当てはめる。

私のアルゴの説明に100%の自信はありませんが、もしこれがそうでないなら、似たようなものでしょう .