減少代碼的運行時間

-1

public class ProjectEuler3 { 
    public static void main(String[] args) { 
     System.out.println(findfactors(600851475143l)); 
    } 

    public static long findfactors(long n) { 
     long[] factors = new long[1000000]; 
     int nooffactor = 0; 

     int c = 0; 

     for (long i = 2; i < n; i++) { 
      if (findPrime(i)) { 
       factors[c++] = i; 
       nooffactor++; 
      } 
     } 

     return factors[nooffactor - 1]; 
    } 

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

來源

2011-06-05 logic101

增加運行時間將意味着使代碼運行_slower_。 – 2011-06-05 19:40:32

啊，歐拉計劃 - 我在想早些時候我應該有另一個破解:)你有什麼想法是什麼讓你的代碼慢？ – marnir 2011-06-05 19:42:40

哦，對於不瞭解歐拉計劃的人，你應該告訴我們代碼應該做什麼！（關於主要因素，這很清楚） – marnir 2011-06-05 19:44:59

你可以嘗試這樣的事情。

private static final BitSet IS_PRIME = new BitSet(); static { 
    IS_PRIME.set(2); 
} 

private static int IS_PRIME_LIMIT = 2; 

public static boolean isPrime(int n) { 
    int p = IS_PRIME_LIMIT; 
    while (p < n) { 
     p++; 
     IS_PRIME.set(p); 
     if (p % 2 == 0) { 
      IS_PRIME.clear(p); 
     } else { 
      for (int i = 3; i * i <= p; i += 2) 
       if (IS_PRIME.get(i) && p % i == 0) { 
        IS_PRIME.clear(p); 
        break; 
       } 
     } 
    } 
    IS_PRIME_LIMIT = p; 
    return IS_PRIME.get(n); 
} 

public static List<Integer> findfactors(long n) { 
    List<Integer> ret = new ArrayList<Integer>(); 
    int sqrtN = (int) Math.sqrt(n); 

    for (int i = 2; n > 1 && i <= sqrtN; i++) { 
     if (isPrime(i)) { 
      while (n > 1 && n % i == 0) { 
       n /= i; 
       ret.add(i); 
      } 
     } 
    } 
    if (n > 1) 
     ret.add((int) n); 
    return ret; 
} 

public static void main(String... args) { 
    // warm up 
    for(int i=0;i<10000;i++) 
     findfactors(600851475143L); 

    // time one lookup. 
    long start = System.nanoTime(); 
    List<Integer> factors = findfactors(600851475143L); 
    long time = System.nanoTime() - start; 
    System.out.println(factors); 
    System.out.printf("Took %.3f ms to find factors%n", time/1e6); 
}

打印

[71, 839, 1471, 6857] 
Took 0.051 ms to find factors

來源

2011-06-06 08:55:31

通過研究分解算法。

來源

2011-06-05 19:41:52 extraneon

考慮記住素數，當他們被計算出來。

來源

2011-06-05 19:43:15

我並不完全確定這個特定問題的要求，但一個性能提升將是改善您的primality test。現在，你正在檢查從2到n。但是，你只需要檢查2到sqrt（n），這將大大減少你檢查的數量，當n是一個大數字。您也無法檢查偶數值大於2

它仍然是簡單的，但這應該得到的性能提升，特別是對於更大的n：

public static boolean findPrime(long n){ 
    int max = (int) Math.ceil(Math.sqrt(n)) 
    for(long i=2; i<max; i++){ 
     if(n%i == 0) { 
      return false; 
     } 
    } 
    return true; 
}

取決於正是你正在嘗試做的，雖然，可能會有更好的解決方案，例如完全不同的解決方法（請參閱Matt Ball's suggestion of a totally different factoring algorithm）。我只是看着你的代碼，並試圖減少操作的數量，而不會在戰略上發生重大變化。

來源

2011-06-05 19:43:29

感謝您的意見 – logic101 2011-06-05 21:40:44

如果兩個是一個因素，那麼你可以保持n除以2直到它不能被整除。這也適用於其他數字。這大大縮短了循環的長度。

預先計算sqrt（n）的所有素數也將有所幫助。

來源

2011-06-05 19:46:56

其實關鍵是要注意的是，你不需要一路走到你原來的紅利。當您找到一個因素時，您將該股息除以該因數（必要時多次），然後增加除數。只要這個數字沒有碰到一些巨大的主要因素（不太可能），這將會非常快。

從技術上講，您只需要搜索到平方根，但出於您的目的，如果您按照上面所述進行操作，則不會有太大的區別。

這裏是一個Scala實現：

def lpf(n: Long, f: Long): Long = { // Largest prime factor function, n = dividend, f = trial divisor 
    if (f * f > n) n      // If divisor squared is bigger than dividend, we have the answer 
    else if (n % f == 0) lpf(n/f, f) // If it divides exactly, divide through and try again with same factor 
    else lpf(n, f + 1)     // Otherwise increase divisor 
    } 
    println(lpf(600851475143L, 2))   // Completes in 1.6 milliseconds

來源

2011-06-05 20:44:13

減少代碼的運行時間

回答

相關問題