与えられた数以上の除数を持つ最小の整数を見つける効率的な方法は何ですか？私が素朴に思うのは、2から始まる数の約数を見つけることです。確かにこれは最善の方法ではありません。答えに近い出発点を推測する方法はありますか？nとそれが持つことができる除数の数との間に何らかの関係があるかもしれません。
質問する
384 次
2 に答える
3
数の素因数分解が次の場合n：
n = p1^a * p2^b * p3^c除数の数は(a + 1) * (b + 1) * (c + 1)です。
これは解決策のヒントです。
問題は見た目ほど単純ではありません。
私は問題を解決する興味深い定理と論文を見つけました：
于 2012-07-28T16:29:04.783 に答える
0
これを行うために、エラトステネスのふるいの適応を使用することを考えましたか? 可能な除数を順番に調べ、適切な点で累積合計に 1 を追加します。たとえば、5 に達したら、5、10、15 の合計に 1 を追加します。これを行うには、コードを大幅に変更する必要はありません。
于 2012-07-28T17:17:40.673 に答える