1

解決策:
コード自体に (おそらく) 「何も問題がない」ことが判明しました。それは非効率的です。私の計算が正しければ、このまま実行すると、2011 年 10 月 14 日金曜日までに完了します。お知らせします。

警告: Project Euler #3 を解決しようとしている場合、ネタバレが含まれる可能性があります。

問題は次のように述べています。

13195 の素因数は 5、7、13、29 です。

600851475143 の最大の素因数は?

これが私の解決策です。私は Java とプログラミング全般を始めたばかりですが、これが最も優れた、または最も効率的なソリューションではないことはわかっています。

import java.util.ArrayList;

public class Improved {
    public static void main(String[] args) {
        long number = 600851475143L;
        // long number = 13195L;
        long check = number - 1;
        boolean prime = true;

        ArrayList<Number> allPrimes = new ArrayList<Number>();

        do {
            for (long i = check - 1; i > 2; i--) {
                if (check % i == 0) {
                    prime = false;
                }
            }

            if (prime == true && number % check == 0) {
                allPrimes.add(check);
            }

            prime = true;
            check--;
        } while (check > 2);

        System.out.println(allPrimes);
    }
}

が13195numberに設定されている場合、プログラムは正常に動作し、[29, 13, 7, 5]という結果が生成されます。

のより大きな値に対してこれが機能しないのはなぜnumberですか?

密接に関連しています (ただし、だまされていません): 600851475143 の「整数が大きすぎます」というエラー メッセージ

4

4 に答える 4

5

コードは非常に遅いです。おそらく正しいですが、許容できないほど長い時間実行されます (n^2/2入力の最も内側のループの反復についてn)。係数を最小から最大の順に計算してみて、次のように各係数を割り出します。

for (i = 2; i*i <= n; ++i) {
  if (n % i == 0) {
    allPrimes.add(i);
    while (n % i == 0) n /= i;
  }
}
if (n != 1) allPrimes.add(n);

このコードは、素数性の明示的なチェックがなくても、素因数のみを追加することに注意してください。

于 2011-02-18T14:49:04.900 に答える
2

ほとんどすべてのプロジェクトオイラーの問題は、64ビットの符号付きデータ型を使用して解決できます（問題13のように意図的に大きくしようとする問題を除く）。

素数を使用する場合（プロジェクトオイラー、素数を使用する場合）は、有利なスタートを切り、エラトステネスのふるい、アトキンのふるい、または サンダラムのふるいを実装します。

多くの問題で使用される数学的トリックの1つは、ターゲットの平方根に作用することにより、検出因子を短絡させることです。二乗よりも大きいものは、二乗よりも小さい係数に対応します。

于 2011-02-18T15:18:34.640 に答える
0

2 からターゲット数の平方根までをチェックするだけで、これを高速化することもできます。各因子は、平方根の上に 1 つ、平方根の下に 1 つずつペアになっているため、1 つの因子を見つけると、それもペアになります。プライムテストの場合、何らかの要因を見つけたら、ループから抜け出すことができます。

もう 1 つの最適化は、因子が素数であることを確認する前に因子を見つけることです。

また、非常に大きな数の場合、特に素数について多くの数をテストしている場合は、力ずくで強制するよりもふるいを使って実験する方が実際には高速です。ふるいを実装するためにアルゴリズム的に非効率的なことをしていないことに注意してください (たとえば、リストから素数を追加または削除すると、余分な O(n) がかかります)。

于 2011-02-18T14:51:20.977 に答える