1234567890の正の約数のうち、5000000以下のものを全て足し合わせたときの和を求めてください。

Question

タイトルの答えを教えてください！ 回答の方よろしくお願いします！
コードはこんなかんじで書きました！
ですが、答えが出てきません。

def divisor_sum(num, limit)
(1..limit).select{ |i| num % i == 0 }.sum
end

puts divisor_sum(1234567890, 50000000)

Comments

[K_3578]

https://teratail.com/help/question-tips
https://teratail.com/help/avoid-asking
とりあえず上記を読みましょう。

後、teratailタグは質問に関係ないので外してください。

[mather]

JavaScriptタグも関係ないので外してください。

[m.ts10806]

何が出てくるんでしょうか。そして何が出てくる想定で組んだのでしょうか。
あと、コードはマークダウンのcodeを利用してご提示ください

[m.ts10806]

タイムアウトしてますね。
数字がでかすぎるんじゃないかな
型とか要確認

Answer 1

5000000以下のもの

puts divisor_sum(1234567890, 50000000)

桁を間違えています。Rubyではアンダースコア _ を挿入しても数値リテラルとして認識してくれるので、記述ミスを減らせます。

# 5,000,000以下のもの
puts divisor_sum(1_234_567_890, 5_000_000)

Answer 2

アルゴリズムの改善案出しときますわ。

1以上limit以下のすべての整数について、numの約数かを調べる必要が常にあるか？といったら無いねんな。題意の和を計算するためには、1以上かつmin { √num を超えない最大の整数, limit } 以下の整数について、num を割り切るか調べれば十分ですわ。

たとえば、質問にあるように num が　1234567890 で、limit が 5000000 のとき、√num を超えない最大の整数は、35136 で、これは 5000000 よりも（かなり）小さく、num を割り切るかどうかのチェックは、1以上35136以下の数に対してだけやれば済むこっちゃ。

以下、考え方の説明します。話を簡単にするため、例えば、numが60、limitが18としますわ。

• 60を割りきるか調べる数（1以上18以下の整数）を変数dとします。

• また、求める合計をsum とします。sum の初期値はゼロです。

• まず、d が 1 のとき、60を割り切るので、sum に 1 を加えます。

• このとき、つまり、numをd が割り切るとき、num ÷ d の商qも num の約数やねんな。num が60でdが1のときは、商qは60で、60は18以下ではないので、この場合はsum には足しませんが、もし商qが 18 以下になっていれば、商も sum に加えます。

• dを、1から順に1つずつ増やして、上記の操作をやっていくと、dが4のとき、qが15になり、初めて商のほうも18以下になりsum に加えることになる。

• 引き続き、d が 5および6のとき、d自身とともに、それらで割った商q として得られる 12および10 も (18以下なので）sum に加えます。

• このような操作によって sum に累積していくとき、dの上限としては、√60 (60の平方根： 7.74...）を超えない最大の整数である7まで調べればよい。（なぜなら、8以上の整数でsum に加算すべきものは、それまでのループの中で、既に商qとして出現しており、その中で limit以下のものは sumに加算済みだから。）

• ただし、num が平方数の場合、たとえば100のとき、√100 は 10なので、d が 10　のとき、商qも 10 になり、limitがたとえば20のとき、上記の操作だと10を２回sumに足してしまうことになるので、重複して足さないようなロジック追加が必要

以上を実装した divisor_sum() のコード例が以下です。ワテ、Rubyは得意やないもんで、javascriptで書いたで。

const divisor_sum = (num, limit) => {
 
  let sum = 0; // 求める合計値
  const sqrtNum = Math.sqrt(num); // num の平方根
  
  for (let d = 1; d <= limit; ++ d) {       
    
    if (d > sqrtNum)  // dがnumの平方根を超えたらループから抜ける
      break;    
    
    if (num % d === 0) {　　// d が num の約数である
      sum += d;　　// sum にdを加算
      const q = num / d;  // sum を d で割った商を求める（整数になる）
      if (q <= limit && q !== d) {  // qがlimit以下であり、かつ qとdが等しくない場合
        sum += q;　　// 商qもsumに加算
      }
    }
  }
  
  return sum;
}


// テスト実行
console.log(divisor_sum(60, 18)); // => 58  (約数かどうかを調べるのは、7までで済む)
console.log(divisor_sum(1234567890, 5000000));　　// => 1734174　(約数かどうかを調べるのは、35136までで済む)
console.log(divisor_sum(100, 30)); // => 67 (約数かどうかを調べるのは、10までで済む。100は10の２乗なので、10を２回足さないようにする。)
console.log(divisor_sum(60, 5)); // => 15 (この場合は、5は√60より小さいので、1以上5以下の全ての整数について60の約数かどうかを調べる)

➡ サンプル

一応、上のコードで // テスト実行 したテストケースは、質問にあるRubyの def divisor_sum(num, limit) でもやってみて、結果が一致したことは確認済みや。

ほなまた〜

Comments

[Zuishin]

> num を割り切るかどうかのチェックは、1以上35136以下の数に対してだけやれば済むこっちゃ。

36070 は 35136 より大きく 5000000 以下で 1234567890 の約数ですが、これを計算に入れなくていいということですか？

[fana]

> ・このとき、つまり、numをd が割り切るとき…(中略)…商も sum に加えます

で扱われる（：36070は，d=34227 でのチェックの時に商として出てくる）形でしょう．

[Zuishin]

> で扱われる（：36070は，d=34227 でのチェックの時に商として出てくる）形でしょう．

なるほど、割り切れるとわかった時だけ割ればいいので除算の回数が減るという意味の回答ですね。

質問は「答えが出てきません」で、回答が「アルゴリズムの改善案」になりますが、これは要するに質問のコードが間違っているので別の数値が出るコードにしたというわけではなく、質問のコードは効率が悪いために正しい答えは出るけどタイムアウトになっているという趣旨の回答でしょうか？

[Zuishin]

なお、タイトルにある 5000000(この回答でも採用されている数値) で試したところ、質問のコードで 1 秒以内に正しい答えが出ました。

[退会済みユーザー]

Zuishin さん, fanaさん
コメントありがとうございます。コメントいただいているご理解と、私がこの回答をした意図との間に齟齬はありません。

[Zuishin]

7 桁を採用するなら mather さんの回答の通り他に何も変えなくても正しい答えが出ますね。
8 桁は Ruby では厳しいようですが、JavaScript ならアルゴリズムを変えなくてもタイムアップにならないんじゃないかと思っています。

Answer 3

残念ながら、ここではコード作成依頼は受け付けておりません。

まずはあなたなりにコードを書いてみましょう。
そのうえで、わからないことがあればそのコードとともに聞いていただければお答えできるかと思います

Comments

[wagadayon]

このような感じでコードを書いたのですが答えが出てこないんですよね

def divisor_sum(num, limit)
(1..limit).select{ |i| num % i == 0 }.sum
end

puts divisor_sum(1234567890, 50000000)

[y_waiwai]

質問文は編集できますんで、それを質問文の方に追記してください。
回答のコメントではあんまし見てくれません

それと、そのコードでは具体的にどういう結果が出るのかを詳しく説明しましょう