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

C++

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

ソースコード

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

int main(void) {

  long long int x = 600851475143;
  int max_prime = 0;
  for (int i = 2; i < int(sqrt(600851475143)); i++)
  {
    if(x % i == 0) {
      x /= i;
      max_prime = i;
    }
  }

  cout << max_prime << endl;

}

/* 実行結果

  6857

*/

答えは6857になりました。

600851475143のルートをとって計算量を少なくしました。

あとは普通のint型ではオーバーフローしたので、long long int 型にしてみました。

少しでも役にたてたら幸いです。

今回は以上になります。

ではまた。

コメント

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