[C++] プロジェクトオイラー Problem5

C++

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

ソースコード

この問題は1〜20までの最小公倍数を求める問題に帰着します。

#include <iostream>
#include <cmath>
using namespace std;

int gcd(int a, int b) {
  int r = 0;
  if (a < b)
    swap(a, b);

  do {
    r = a % b;
    a = b;
    b = r;
  } while (r > 0);

  return a;
}

int main(void) {

  long long int a = 1;

  for (int i = 1; i <= 20; i++) {
    a = i * a / gcd(a, i);
    cout << i << "回目: "<< a << endl;
  }

  cout << a << endl;


}

最初に18044195という結果がきました。

原因はaをint型にしていたからでlong long int型にしたら232792560になり正しい結果になりました。

おそらくオーバーフローしていたからですかね。

てことで今回は以上になります。

ではまた。

コメント

タイトルとURLをコピーしました