十進ベーシックで約数の和を求める

自然数nを入力すると、自身を除く約数の和を求めるプログラムをつくる。
という問題がわかりません。
十進ベーシックを使ってのプログラムを教えていただきたいです。
宜しくお願い致します。

質問者からの補足コメント

• 1も約数に入ります。例えばn＝8であれば、1+2+4=7になります。

  No.1の回答に寄せられた補足コメントです。 補足日時：2019/01/29 21:43

No.1 回答者： GOMΛFU 回答日時： 2019/01/29 20:21

1も約数に入るの?

No.2 回答者： Tacosan 回答日時： 2019/01/30 00:01

n=8 に対して 1 を約数に入れるのに 8 が約数に入らないのが謎.

そしてどこで困っているのだろうか.

No.3 ベストアンサー 回答者： stomachman 回答日時： 2019/01/30 00:18

完全数でもお探しなのか。

どういうレベルの解をお求めなのかによって、難易度はかなーり違うんです。

　一番簡単な解は、
　　　合計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が巨大である（たとえば何千桁とかの）場合、素因子分解は結構大変なんですよね。なにしろ素因子分解の大変さは暗号に応用されるぐらいですから。
　というわけで、どういうレベルの解をお求めなのかによって、難易度はめっちゃ違うんですけど。

この回答へのお礼

ありがとうございます！
がんばってみます！

お礼日時：2019/02/10 00:36