1 
public class prime
{
   public static void main(String[] args)
    {
     long thing = 600851475143L;
     for(long i = 300425737571L ; i == 0 ; i-- ){
     if (thing % i == 0)
     {
       long answer = i;
       System.out.println(answer);
       break;
     }
     }

    }

}

これは私が現在持っているコードですが、DrJavaで数分間実行しましたが、結果が返されませんでした。私のコードを最適化する方法はおよそ100万通りあると思いますが; 誰かが私にいくつかのヒントを与えることができますか？

今日、いくつかのプログラミングの問題を解決しようとしていますが、これは私にいくつかの問題を引き起こしています。

どうもありがとう ：）

4

3 に答える 3

3

極端に大きくない値で素因数を計算するには、「もの」の平方根までの素因数を生成してから、それらを1つずつ試す方がはるかに効率的です。

素数の生成が行われる場合があります。

于 2010-10-23T11:12:55.850 に答える
3

ただし、sqrt（thing）まで繰り返す必要があります。

そして、一般的には、2から開始する方が速くなります。これは、数値の半分が2倍（および1/3が3倍など）になるためです。

また、最初の要素だけを壊しているので、他の要素を見逃します

 long thing = 600851475143L;
 for(long i = 0; i < 300425737571L ; i++ ){
     if (i * i > thing) {
       break;
     }
     if (thing % i == 0) {
       long answer = i;
       System.out.println(answer);
       break;
     }
 }
  • aioobeが言うように、より洗練された方法が利用可能です
于 2010-10-23T11:13:13.770 に答える
2

いいえ、すぐに終了します。

i == 0

最初の反復では保持されません。

あなたはおそらくこのようなものを書きたいと思ったでしょう：

public class Test {
    public static void main(String[] args) {
        long thing = 600851475143L;
        for (long i = 16857 /* 300425737571L */; i > 0; i--) {
            if (thing % i == 0) {
                long answer = i;

                // Print the largest prime factor, then break loop (and quit)
                System.out.println(answer);
                break;
            }
        }
    }
}

ただし、この単純な因数分解方法は非常に非効率的です。の因数分解は60085147514330042573757171 * 839 * 1471 * 6857から6857まで反復し、毎回モジュロを実行する必要があるためです。長い間、一瞬で因数分解を解くような複雑な方法はたくさんありますが、それほど複雑ではありません。

于 2010-10-23T10:59:48.493 に答える