[解決済み] Project Euler #3 Javaによる解答問題

質問内容

class eulerThree {

    public static void main(String[] args) {

        double x = 600851475143d; 

        for (double z = 2; z*z <= x; z++) {

            if (x%z == 0) {

                System.out.println(z + "PRIME FACTOR");

            }

        }

    }

}

と出力されます。

71.0
839.0
1471.0
6857.0
59569.0
104441.0
486847.0

つまり、私は486847がxの最大の素因数であると仮定していますが、project eulerはそうではないと述べています。私のコードや数学に問題があるとは思えないので、かなり混乱しています。何かお分かりになることがありますか？

どのように解決するのですか？

まず、正確な演算手段を使うことです。他の方の提案では BigInteger . これはやってもいい。私にとっては、これはちょっとズルい感じがするので（これは、もっと大きな整数を扱う後の問題でより重要になります）、（私の考えでは）より楽しい方法は、必要な任意精度演算を自分で書くことです。

次に、600851475143は十分に小さいので、そのような場合は long の方がはるかに速いでしょう。

第三に、このループは素因数分解を正しくチェックしていません。奇数だけをチェックしているのです。これは素（不完全）な解決策です。

long num = 600851475143L;
List<Long> factors = new ArrayList<Long>(); // or use a Set
if (num & 1 == 0) {
  factors.add(2L);
}
for (long i=3; i*i<=num; i+=2) {
  // first check i is prime
  // if i is prime check if it is a factor of num
}

素質があるかどうかのチェックは、さまざまなレベルで実装されています。最も単純なものは

public boolean isPrime(long num) {
  for (long i=2; i<=num; i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

もちろん、これではいろいろと無駄なチェックをすることになります。すでに判断したとおり、チェックするのは sqrt(n) で、偶数（2以外）を排除することができます。

public boolean isPrime(long num) {
  if (num & 1 == 0) {
    return false; // checks divisibility by 2
  }
  for (long i=3; i*i<=num; i+=2) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

しかし、これよりももっと良い方法もあるはずです。もうひとつの最適化は、数値をチェックするのは 素数 その範囲内で 63の素因数は3と7です。もしある数字が3か7で割り切れないなら、それは63で割り切れないという定義になる。

つまり、あなたがやりたいことは、おそらく Set<Long> または素数の2乗が目標数以上になるまで。そして、この一連の数字が目標の数字に割り切れるかどうかをチェックするだけです。