[解決済み] 与えられた数の除数の数を計算するアルゴリズム
質問
与えられた数の約数を計算するために、最も最適なアルゴリズム(パフォーマンス的に)は何だろう?
疑似コードやサンプルへのリンクを提供していただけると幸いです。
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%の自信はありませんが、もしこれがそうでないなら、似たようなものでしょう .
関連
-
[解決済み] なぜベクトル化、ループよりも一般的に速いのですか?
-
[解決済み] LOWER LIKE vs iLIKE
-
[解決済み] callとapplyの違いは何ですか?
-
[解決済み] SQLiteのINSERT/per-secondのパフォーマンスを向上させる
-
[解決済み] ゲーム「2048」の最適なアルゴリズムとは?
-
[解決済み] JavaScriptでオブジェクトのキー/プロパティの数を効率的にカウントする方法
-
[解決済み] 簡単な面接問題が難しくなった:1~100の数字が与えられたとき、ちょうどk個の数字が欠けていることを見つけなさい。
-
[解決済み] ビッグ・オー、どうやって計算・概算するんだ?
-
[解決済み】画像処理。コカ・コーラ缶」認識のためのアルゴリズム改良
-
[解決済み】再帰と反復のどちらを選ぶ?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み] なぜベクトル化、ループよりも一般的に速いのですか?
-
[解決済み] 効率的なアウトオブコアソーティング
-
[解決済み】2つの範囲が重なっているかどうかをテストする最も効率的な方法は何ですか?
-
[解決済み】ウェブサイトのストレステストに最適な方法【重複あり
-
[解決済み] Scalaのlazy valの(隠れた)代償は何なのか?
-
[解決済み] Apache Spark: map vs mapPartitions?
-
[解決済み] x86アセンブリでレジスタをゼロに設定するには、xor、mov、andのどれが一番良い方法ですか?
-
[解決済み】2次元の点がポリゴン内にあるかどうかを判断するにはどうしたらいいですか?
-
[解決済み] フィボナッチヒープを実際に効率よく実装した人はいますか?
-
[解決済み] TeamViewerはどうしてこんなに速いのですか?