No.3ベストアンサー
- 回答日時:
完全数でもお探しなのか。
どういうレベルの解をお求めなのかによって、難易度はかなーり違うんです。一番簡単な解は、
合計sを0にする。
nをk=1〜n-1で順番に割ってみて、割り切れたらsにkを加える。
でしょう。
あまりにも芸がない(nが大きくなると時間がかかる)のでもうちょっとなんとかしたい、とすると(つまり約数をもう少し早く見つけられないか、ということですが)、nより小さい最大の約数は√n以下である、ということを使って、
hを√nを超えない最大の整数にする。合計sを1にする。
nをk=2〜hで順番に割ってみて、割り切れたらsにkを加える。
最初のに比べれば√n倍のスピードアップ。さらに、n÷k = q (余りなし)の場合、kだけでなくqもnの約数である、ということを使うと、
合計sを1にする。
k=2にする。
以下繰り返す:
nがkで割り切れるなら、その商をqとし、sにk+qを加え、kを1増やす。
k≧qなら繰り返しを終わる。
とやれば、さらに2倍のスピードアップ。
いやもう、そんなちまちましたやり方ではなくて、もっと本格的にスピードアップしたいのであれば、nを素因子分解して n = (f[1]^p[1]) (f[2]^p[2]) … (f[m]^p[m]) となる f[1], f[2], … , f[m], p[1],p[2],…,p[m] をみつけておいて、これらの組み合わせの総和を作るのが良いでしょう。nが小さいのであれば、あらかじめ√nまでをカバーする素数のリストを作っておけば簡単に計算できる。nが十何桁程度なら楽勝。けれども、nが巨大である(たとえば何千桁とかの)場合、素因子分解は結構大変なんですよね。なにしろ素因子分解の大変さは暗号に応用されるぐらいですから。
というわけで、どういうレベルの解をお求めなのかによって、難易度はめっちゃ違うんですけど。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# c言語で自然数nを入力、2以上n以下の偶数の累積sumを求めるプログラムをfor文を使って作りたいで 4 2022/11/09 14:10
- C言語・C++・C# C言語階乗の総和を求める 2 2023/03/04 23:31
- 数学 群数列の問題がわかりません。どなたか教えてください… 【問題文】 1から順に自然数を並べて, 下のよ 2 2022/03/28 18:55
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- C言語・C++・C# 【CASLプログラム】 定数(80と55)を確保し、その和をGR1に、その差をGR2に求めるCASL 1 2022/12/16 01:17
- Ruby VBA 2 2023/01/14 14:14
- C言語・C++・C# 3つの倍精度浮動小数点値の平均を求めて、3つの引数全てを平均値に変更するメソッドを作成し、キーボード 1 2022/07/13 16:04
- 大学受験 至急! 数学 整数 なぜ3以上にならないのですか? 3 2023/01/29 12:47
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 malloc関数を使ってください!お願いします! 最 1 2022/07/21 09:28
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
大学のレポートA42枚以上と言わ...
-
加速度センサーを用いて計測を...
-
gsと略される大学ってありますか?
-
昔より技術大国とは言えなくな...
-
酸化と還元って同時に起きますよね
-
千葉工業大学は東京大学と繋が...
-
信管を無効化する技術ってあり...
-
2の累乗の枚数のトランプやカル...
-
恨みを消す為にはどうしたらい...
-
この花の名前を教えて下さい
-
大学レベルの情報工学が学べる...
-
GMARCHや関関同立でマーク式が...
-
数理科学ていう雑誌は
-
国立大学の女子の数について
-
【あなたが知っているHaptics(...
-
昔とった国家資格や試験、大学...
-
通信制大学
-
ALPSの処理水の海洋放出は危険...
-
素数の無限この証明って
-
ハノイの塔のさいきアルゴリズ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「0 < x ≦ y ≦ zである整数x, y...
-
逆関数を持つための条件につい...
-
a人が1人400円ずつ出して、b円...
-
x²+y²≦10を満たす整数x、yの組(...
-
留数 ローラン級数
-
一次不等式が分かりません
-
数学の問題で、「間に成り立つ...
-
ノルムについて。
-
正の数負の数でどうしてものこ...
-
1≦k≦(2^m)-1を満たす奇数kは、2...
-
「互いに素であるA、B」と 「...
-
場合の数
-
相加相乗平均等号成立について
-
条件付きの最小値(高校数学)
-
[x] は,正の整数xの正の約数の...
-
チャート式数学難問集の整数問...
-
十進ベーシックで約数の和を求める
-
√3が無理数であることを用いて...
-
困数分解と 云いたい
-
青チャート 整数の性質 練習 (3...
おすすめ情報
1も約数に入ります。例えばn=8であれば、1+2+4=7になります。