3

http://projecteuler.netから問題 3 を解決しようとしています。ただし、プログラムを実行しても何も出力されません。私は何を間違っていますか？問題: 数 600851475143 の最大の素因数は?

public class project_3 
{
    public boolean prime(long x)   // if x is prime return true
    {
        boolean bool = false;

        for(long count=1L; count<x; count++)
        {
            if( x%count==0 )
            {
                bool = false;
                break;
            }
            else { bool = true; }
        }
        return bool;
    }

    public static void main(String[] args)
    {
        long ultprime = 0L;  // largest prime value
        project_3 object = new project_3();

        for(long x=1L; x <= 600851475143L; x++)
        {
            if( object.prime(x)==true )
            {
                ultprime = ((x>ultprime) ? x : ultprime);
            }
        }
        System.out.println(ultprime);
    }
}
4

3 に答える 3

6

primeチェック関数が常に返すだけではありませんfalse。正常に機能していたとしても、メイン ループは入力数値の因数をまったく求めず、それより小さいか等しい最大の素数だけを求めます。疑似コードでは、コードは次と同等です。

foo(n):
    x := 0 ;
    foreach d from 1 to n step 1:
        if is_prime(d):          // always false
            x := d
    return x                     // always 0

is_prime(d):
    not( d % 1 == 0 )            // always false

しかし、ここではプライムチェック機能はまったく必要ありません。以下は、試行分割によって、数値のすべての要因を見つけます。

factors(n):
    fs := []
    d  := 2
    while ( d <= n/d ):
        if ( n % d == 0 ): { n := n/d ; fs := append(fs,d) }
        else:              { d := d+1 }
    if ( n > 1 ): { fs := append(fs, n) }
    return fs

割り切れるかどうかのテストは、数の平方根までしか行われません。見つかった各因数は因数分解された数から除算されるため、実行時間がさらに短縮されます。問題の数の因数分解は、わずか 1473 回の繰り返しで即座に実行されます。

構造上、こうして見つかったすべての因子は素数であることが保証されます (そのため、素数チェックは必要ありません)。これを実現するには、考えられる除数を昇順に列挙することが重要です1。昇順も最も効率的です。これは、任意の数値が大きい素因数よりも小さい素因数を持つ可能性が高いためです。オッズの代わりに素数を列挙することは、必須ではありませんが、これらの素数を効率的に取得して除算をテストする方法があれば、より効率的です。

最大の要因を見つけるために上記を拡張するのは簡単です:appendとして実装するだけです.

append(fs,d):
    return d

1因数分解される元の数の 任意の合成約数dについて、 に達するdと、元の数からその素因数を既に分割しているため、簡約された数には共通の素因数がありません。つまり、d勝ちました。元を割りますが、減数を割りません。

于 2013-03-08T11:26:58.150 に答える
3

2つのこと：

1) count2 ではなく 1 から始めています。すべての整数は 1 で割り切れます。

2）かなり大きなNに対してO（n ^ 2）アルゴリズムを実行しています（または、少なくともポイント＃1を修正するとそうなります）。実行時間はかなり長くなります。

于 2013-03-07T18:52:37.943 に答える