java - Project Euler #3 は Java で永遠にかかります

Question

Project Euler の問題 3 は次のとおりです。

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

600851475143 の最大の素因数は?

私の解決策は永遠にかかります。私は正しい実装を得たと思います。ただし、大きな数でテストすると、結果を見ることができませんでした。それは永遠に実行されます。私のアルゴリズムに何か問題があるのだろうか：

public class LargestPrimeFactor3 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;
        long pFactor = 0;

        start = System.currentTimeMillis();

        for(int i = 2; i < num; i++) {
            if(isPrime(i)) {                
                if(num % i == 0) {
                    pFactor = i;                        
                }
            }
        }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println(pFactor + " Time: "+totalTime);
    }

    static boolean isPrime(long n) {

        for(int i = 2; i < n; i++) {
            if(n % i == 0) {
                return false;
            }
        }        
        return true;
    }     
}

score 5 · Accepted Answer

Javaではありませんが、おそらく次のことがわかると思います。基本的に、奇数の約数と数の平方根までをテストするだけで反復を削減する必要があります。これは、C# で即座に結果が得られるブルートフォースアプローチです。

static bool OddIsPrime (long oddvalue)  // test an odd >= 3 
{
    // Only test odd divisors.
    for (long i = 3; i <= Math.Sqrt(oddvalue); i += 2)
    {
        if (value % i == 0)
            return false;
    }
    return true;
}

static void Main(string[] args)
{
    long max = 600851475143;   // an odd value
    long maxFactor = 0;

    // Only test odd divisors of MAX. Limit search to Square Root of MAX.
    for (long i = 3; i <= Math.Sqrt(max); i += 2)
    {
        if (max % i == 0)
        {
            if (OddIsPrime(i))  // i is odd
            {
                maxFactor = i;
            }
        }
    }
    Console.WriteLine(maxFactor.ToString());
    Console.ReadLine();
}

score 3 · Accepted Answer

見つかった各要因を分割する必要があります。次に、可能な約数を昇順で列挙するときに素数性をテストする必要はありません (このように見つかった約数は合成することはできません。その約数は既に分割されています)。コードは次のようになります。

class LargestPrimeFactor4 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;   // odd value is not divided by any even
        long pFactor = 1L;

        start = System.currentTimeMillis();

        for(long i = 3L; i <= num / i; ) 
        {
            if( num % i == 0 ) {
                pFactor = i;
                num = num / i;
            }
            else {
                i += 2;
            }
        }
        if( pFactor < num ) { pFactor = num; }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println( pFactor + " Time: " + totalTime);
    }
}

score 2 · Accepted Answer

public HashSet<Integer> distinctPrimeFactors(int n) //insane fast prime factor generator
{
    HashSet<Integer> factors = new HashSet<Integer>();
    int lastres = n;
    if (n==1)
    {
        factors.add(1);
        return factors;
    }
    while (true)
    {
        if (lastres==1)
            break;
        int c = 2;
        while (true)
        {
            if (lastres%c==0)
                break;
            c++;
        }
        factors.add(c);
        lastres/=c;
    }
    return factors;
}

数値の個別の素因数をすばやく生成したい場合は、反復ごとに数値を小さくするこの方法を使用します。int を long に変更すると、うまくいくはずです。

score 1 · Accepted Answer

試行除算による整数因数分解の擬似コードは次のとおりです。

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    output n

これを理解する最も簡単な方法は、例です。n = 13195 の因数分解を考えてみましょう。最初は z = 2 ですが、13195 を 2 で割ると余りが 1 になるため、else 節で z = 3 を設定し、ループします。現在、n は 3 でも 4 でも割り切れませんが、z = 5 の場合、13195 を 5 で割った余りがゼロになるため、5 を出力して 13195 を 5 で割ると、n = 2639 で z = 5 は変更されません。ここで、新しい n = 2639 は 5 または 6 で割り切れませんが、7 で割り切れるので、7 を出力して n = 2639 / 7 = 377 に設定します。次に、z = 7 を続けます。除算と同様に剰余が残ります。 8、9、10、11、12 で計算しますが、377 / 13 = 29 で余りがないので、13 を出力して n = 29 に設定します。この時点で z = 13 で、z * z = 169 です。 29 より大きいので、29 は素数であり、13195 の最終因数であるため、29 を出力します。完全な因数分解は 5 * 7 * 13 * 29 = 13195 です。

試行除算を使用して整数を因数分解するためのより優れたアルゴリズムと、試行除算以外の手法を使用して整数を因数分解するためのさらに強力なアルゴリズムがありますが、上記のアルゴリズムで始めることができ、Project Euler #3 には十分です。詳細については、こちらをご覧ください。

score 0 · Accepted Answer

パフォーマンスを向上させるための 2 つのこと:

static boolean isPrime(long n)
{
    for(int i = 2; i <= sqrt(n); i++)  // if n = a * b, then either a or b must be <= sqrt(n).
    {
        if(n % i == 0)
        {
            return false;
        }
    }        
    return true;
}

次にメインループ

for(int i = num; i > 1; i--) // your interested in the biggest, so search from high to low until you have a match
{
    if(num % i == 0 && isPrime(i)) // check for num % i == 0 is faster, so do this first
    {
        pFactor = i;
        break; // break if you have a factor, since you've searched from the top
    }
}

ここで改善できることはまだありますが、それはあなた次第です。変更することを考えてくださいnum。プロジェクトオイラーを楽しんでください:)

score -1 · Accepted Answer

これは完璧に機能します!!

public class Puzzle3 {
public static void main(String ar[])
{
    Long i=new Long("1");
    Long p=new Long("600851475143");
    Long f=new Long("1");
    while(p>=i)
    {
        if(p%i==0)
        {
            f=i;
            p=p/i;
            int x=1;
            i=(long)x;
        }
        i=i+2;
    }
    System.out.println(f);
}

}

score -1 · Accepted Answer

public class LargestPrimeFactor {
    static boolean isPrime(long n){
        for(long i=2;i<=n/2;i++){
            if(n%i==0){
                return false;                                               
            }
        }
        return true;    
    }

    static long LargestPrimeFact(long n){
        long largestPrime=0;
        for(long i=2;i<Math.sqrt(n)/2;i++){
            if(n%i==0){
                if(isPrime(i)){
                    largestPrime=i;
                }
                }                                       
            }
        return largestPrime;
    }
    public static void main(String args[]) {
        System.out.println (LargestPrimeFact(600851475143L));
    }
}

ソース: http://crispylogs.com/project-euler-problem-3-solution/

java - Project Euler #3 は Java で永遠にかかります

9 に答える 9

Related

Reference