2

私は Java でコーディングすることを学び始めました。そして、Project Eulerサイトを使用して、学習した新しいコーディングの各ビットを試して完了するための小さなタスクを与えることにしました。だから私は問題3に出くわしました:

13195 の素因数は 5、7、13、29 です。600851475143 の最大の素因数は?

私はこの問題について考え、素数に関するさまざまな理論と、さまざまな計算 (エラトステネスのふるいがその例です) を介して素数を見つける方法についてさまざまな理論を調査しました。それらが素数だった場合、Tn 変数 (この場合は 600851475143) を新しく発見された素数で割り、それが因数であるかどうかを確認します。そうであれば、それを変数 Hp (最高素数) に割り当て、プログラムの最後に Hp をコンソールに出力して結果を出します。

これが私のコードです：

public class Largest_Prime_Factor_NEW_SOLUTION {

    static long Tn = 600851475143L;
    static long Hp = 0;
    static boolean isPrime = false;

    public static void main(String[] args) {

        for (long i=2; i<Tn; i++) {
            System.out.println("TESTING NUMBER " + i);
            for (long k=2; k < i; k++) {
                if (i % k == 0) {
                    System.out.println(i + " IS NOT A PRIME");
                    break;
                } else if (k + 1 == i) {
                    isPrime = true;
                }
            }

            if (isPrime) {
            System.out.println(i + " IS A PRIME");
            if (Tn % i == 0) {
                System.out.println(Tn + " IS DIVISIBLE BY " + i);
                Hp = i;
            } else {
                System.out.println(Tn + " IS NOT DIVISIBLE BY " + i);
            }
            }

            isPrime = false;
        }
        System.out.println("THE HIGHEST PRIME NUMBER OF " + Tn + " IS " + Hp);
    }
}

今、私はこのコードが非常に非効率的であることを知っており、開始したところからコードを要約することができました (どこにでもループがありました!)。私が研究することはすべて他の人がすることと矛盾していて、非常に混乱しているので、それは私を蝕んでいます. sieve メソッドを試してみましたが、ブール配列は int 配列にしかならず、long 配列にはならないことを理解していますか?

コーディングを始めるときは、使える知識に制限があることは理解していますが、興味があるだけで、最終的な解決策がどうなるかを知りたいと思っています。

4

6 に答える 6

6

あなたができることは、 の最小の約数を見つけることですTn。が であると仮定しp、 の最小の約数を再度見つけますTn/p。

さて、すべてのステップpで素数です[以下の説明]。したがって、それらを集めると、それらは の素約数になりTnます。

ceil(sqrt(Tn))時間の複雑さを改善するために、 の代わりにupto までの除数のみをチェックできますTn-1。

の素因数のチェックを開始するときは、 から開始Tnできます2。そして、素因数を取得したら、forpから再度開始しないでください。は の約数でもあり、はより小さい約数を持たないため、もそれを持ちません。だから、もう一度[複数の力を持つことができる]から始めましょう。が分割されていない場合は、 に移動します。2Tn/pTn/pTnTnpTn/pppTnpTnp+1

例 ：

Tn = 45 1. 2 から始めます。2 は 45 を割り切れ
ません。2. 次のテストは 3 です。 3. 45/3 = 15 の素約数をチェックしますが、2 からではなく 3 から始めます。4. 15 は 3 で割り切れます。15/3 = 5 から始めます。 5. 5 の場合、ceil(sqrt(5)) は 3 です。 5)) そして、5 は間違いなく素数であると言えます。

したがって、45 の素約数は 3 と 5 です。

数の最小の約数 (1 を除く) が素数であるのはなぜですか?

上記のステートメントが偽であるとします。その場合、数値 N は、C などの最小の合成約数を持ちます。

つまり C|N C は合成なので、それ自体よりも小さいが 1 よりも大きい除数を持ちます。
そのような C の約数をP とします。
つまり P|C ですが、1 < P < C の場合、C|N => P|N となります。

これは、C が N の最小の約数であるという仮定と矛盾するため、数値の最小の約数は常に素数です。

于 2013-07-21T10:40:11.980 に答える
0

このようなプログラムを改善するには多くの方法がありますが、改善は主にプログラミングではなく数学に関係しています。

  • 因数を探すときは、素数だけでなく、それぞれの数を調べてください。因数が見つかったら、それが素数かどうかを確認します。このようにして、多くの素数チェックを回避できます。

  • 合成数の最大の素因数は最大で数の平方根になるため、反復を早期に停止できます。

  • 試行分割を行う代わりに、素早い素数性テストを使用してください http://en.wikipedia.org/wiki/Primality_test

繰り返しますが、これは 1 回限りです。複雑にしないでください。

于 2013-07-21T10:56:22.493 に答える
0

これは学習演習として行っているため、現在のプログラムを十分に改善したら、同じ問題を別の方法で解決してみませんか? フェルマー因数分解法は、最初に大きな因数を見つけます。

于 2013-07-21T11:06:30.110 に答える
0

試行分割による合成数の素因数分解の単純なアルゴリズムは次のようになります。

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            fs.append(f)
            n := n / f
        f := f + 1
    if n > 1
        fs.append(n)
    return fs

そのアルゴリズムは改善することができ、大きな数を素因数分解するためのより優れたアルゴリズムがありますが、それはあなたのタスクには十分です。より多くの準備ができたら、私のブログでエッセイ「 素数を使用したプログラミング」をお勧めします。これには、Java でのそのアルゴリズムやその他の実装が含まれています。

于 2013-07-21T12:25:33.070 に答える