1

元々、このコードを機能させるのに問題がありましたが、少し調整した後、デバッグして準備が整いました。

私はこのプログラムのいくつかの改訂を経験しました。私は整数値から始めましたが、数値が大きすぎてintに収まらないことがわかりました。次に、BigIntegersに変更しました。これは面倒ですが、実行可能であることがわかりました。そこから、（最初から行うべきだったように）longに切り替えて、コードの実行時間を8分の1（またはそれ以上）に短縮しました。

現在のコードは次のとおりです。

long qNum = 600851475143L;

for (long i = qNum - 1L; i * i >= qNum; i -= 2L)
    if (qNum % i == 0 && isPrime(i)) {
        System.out.println("Solution:" + i); // for debugging
        return i;
    }
    else
        System.out.println(i);// for debugging

return 0L;

と

public static boolean isPrime(long num) {
    // unnecessary if statement for this problem (b/c of for loop), but useful for others 
    if (num % 2 == 0)
        return false;

    for (long i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;

    return true;
}

何時間も実行されていますが、まだ何も見つかりません。このパズルを解く典型的な方法は、560GBのデータを解析するようなものだとオンラインで見ました=/。

これをスピードアップするためのヒントはありますか？

どうもありがとう、

ユスティニアヌス

編集：

最適化されたコード：

public static long greatestPrimeFactor(ArrayList<Long> factors, long num) {
    for (long i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            factors.add(i);
            return greatestPrimeFactor(factors, num / i);
        }
    }

    for (int i = factors.size()-1; i > 0; i--)
        if (isPrime(factors.get(i)))
            return num;

    return 0;
}

と

public static boolean isPrime(long num) {
if (num % 2 == 0)
    return false;

for (long i = 3; i * i <= num; i += 2)
    if (num % i == 0)
        return false;

    return true;
}

で実行

greatestPrimeFactor(new ArrayList<Long>(), 600851475143L);
4

4 に答える 4

3

私のソリューションは100分の1秒未満でヒットします。数の約数を見つけるたびに、その数をその約数で割って、最初からやり直してください。あなたが割る最大の数はあなたの目標です。

于 2010-07-28T19:14:37.973 に答える
3

You are doing too many unnecessary things. Here's a simpler solution: 

long greatestFactor(long n) {
    long p = 0;
    for (long k = 2; k * k <= n; k++)
        while (n % k == 0) {
            n /= k;
            p = k;
        }
    if (n > 1)
        p = n;
    return p;
}
于 2010-08-29T22:24:04.527 に答える
0

素数であるかどうかについて、すべての数値をテストする必要はありません。これが表示されるので、すべてのODD番号（および2）のみをテストします。これをさらに進めることができます！最初の数百万の素数のテーブルをすばやく作成し、それらに対してのみテストします。非常に小さなオーバーヘッドで、はるかに速く進みます。

編集：これが私が話していたことです。それは非常に簡単です。値をすでに計算された素数とのみ比較する方法に注意してください。それらのかなりの数（たとえば、最初の10000000素数）を計算したら、あなたと同じように+2メソッドに基づいて検索を開始します。あなたが不必要な数をスキップしているので、それらのほとんどは早く捕まるだろうということを覚えておいてください。すでに5をテストしているので、15、25、35、45、55などをテストする必要はありません。それ自体でテストの約20％がカリングされ、計算のオーバーヘッドを簡単に説明できます。最初の数百万の数字。

サンプル出力

C:\files\j\misc>java sandbox2
resized to 200
resized to 400
resized to 800
resized to 1600
resized to 3200
resized to 6400
resized to 12800
resized to 25600
resized to 51200
resized to 102400
resized to 204800
resized to 409600
resized to 819200
664579 primes in 18 seconds. Last prime was 9999991

C:\files\j\misc>

サンプルコード：

public class sandbox2 {
    static int[] primes = new int[100]; // where the primes really are
    static int count = 0;
    static long mostRecentPrime;

    public static void main(String[] args) throws Exception {
        addPrime(2); // give it a couple to start
        addPrime(3);
        addPrime(5);
        long start = System.currentTimeMillis();
        for(long i = 7; i < 10000000; i++) { // all primes less than 10M
            if(isPrime(i)) addPrime(i);            
        }        
        long end = System.currentTimeMillis();
        long time = (end-start) / 1000;
        System.out.println(count + " primes in " + time + " seconds. Last prime was " + mostRecentPrime);
    }    
    public static boolean isPrime(long i) {
        long max = (long)(Math.sqrt(i))+1;
        for(int pos = 0; primes[pos] < max && pos < primes.length; pos++) {
            long prime = (long)(primes[pos]);
            if(i % prime == 0) return false;
        }
        return true;
    }    
    public static void addPrime(long p) {
        mostRecentPrime = p;
        if(count == primes.length) { // resize if necessary
            int size = primes.length * 2;
            int[] newprimes = new int[size];
            System.arraycopy(primes, 0, newprimes, 0, primes.length);
            primes = newprimes;
            System.out.println("resized to " + primes.length);
        }
        primes[(int)count] = (int)p;
        count++;
    }
}
于 2010-07-28T19:15:18.430 に答える
0

Python では、すべての素因数を計算してから、次のように max 関数を使用できます。

def calc_prime_factors(n,i=2,result=[]):
  while i<=n:
    while n%i!=0:
      i+=1
    result.append(i)
    if n!=1:
      n,i=n/i,2
    else:
      break
  return result

print max(calc_prime_factors(600851475143))
于 2014-09-22T21:17:35.250 に答える