kostumブログ

勉強したことやノート代わりのアウトプットに使っています。

project Euler 003

環境

問題

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

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

考え方

  1. 求めたい数を変数に入れる(ここでは、numとする)
  2. numの平方数を算出し、整数値を取得する

    *numの平方数以上のnumの約数は、numの平方数以下のnumの約数と対になっているため

  3. numの平方数から 1 までの剰余を計算し、0の時を求める

  4. 2.で求めた数を、さらに 3 から 2. で求めた数の平方数までの剰余を計算する
  5. 割りきれた場合、その数は素数でないので、ループを離脱
  6. 割り切れる数がなかった場合、その数は素数なので、条件分岐用変数に true を代入
  7. ループの最後に、割り切れた数が素数がどうかをチェックする

コード

const question003 = () => {
    let num = 600851475143;
    let numSqrt = Math.floor(Math.sqrt(num));
    let max = 1;
    let isSosu = false;
    for (let i = numSqrt; i > 1; i--) {
      if (num % i == 0) {
        for (let j = 3; j <= Math.floor(Math.sqrt(i)); j = j + 2) {
          if (i % j == 0) {
            isSosu = false;
            break;
          } else {
            isSosu = true;
          }
        }
        if (isSosu) {
          max = i;
          return max;
        }
      }
      if (isSosu) {
        break;
      }
    }
    return max;
  };

説明

  • まず、必要な変数を設定する
  • 最大値を求めたいので、600851475143 からループ計算を始める
  • ただ、numの平方数以上のnumの約数は、numの平方数以下のnumの約数と対になっているため、600851475143 の平方数の整数値(平方数とする)を取得し、その数からループ計算を始める
  • 600851475143 を平方数で割っていき、割り切れた場合、その平方数が素数かどうかをチェックする
  • 素数をチェックするには、3 ~ 割り切れた数の平方数の間の数で割り、割り切れた場合、その数は素数でなく、ループを離脱する
  • 一度も割り切れなかった場合、その数は素数となるので、全てのループを終了する