計算素數因子分解的更有效方法是什麼？

我目前有一個程序來查找給定數字的素因式分解;使用較小的數字可以正常工作，但超過一百萬年的時間需要很長時間。我的代碼效率極低，找到輸入下方的所有素數並檢查哪些分數沒有餘數。我不知道如何讓它效率低下，有什麼幫助？計算素數因子分解的更有效方法是什麼？

static ArrayList<Integer> primeNumbersBelow(long n) { 

    ArrayList<Integer> ay = new ArrayList<Integer>(); 
    ay.add(2); 

    for(int i = 3; i < ((n % 2 != 0) ? (n + 1)/2 : n/2); i++) { 
     boolean divides = false; 
     for(int j = 2; j < i; j++) { 
      if(i % j == 0) { 
       divides = true; 
      } 
     } 
     if(!divides) { 
      ay.add(i); 
      System.out.println(i); 
     } 
    } 
    return ay; 
} 

static ArrayList<Integer> primeFactorisationOf() { 

    ArrayList<Integer> ay = new ArrayList<Integer>(); 
    ArrayList<Integer> aay = primeNumbersBelow(input); 
    long n = input; 

    for(int i = 0, len = aay.size(); i < len; i++) { 
     int f = aay.get(i); 
     boolean run = true; 

     while(run) { 
      if(n % f == 0) { 
       ay.add(f); 
       n /= f; 
      } else { 
       run = false; 
      } 
     } 
    } 
    return ay; 
}

來源

2015-03-31 platelminto

從Mr Lars Vogel @ vogella ...

public static List<Integer> primeFactors(int number) { 
    int n = number; 
    List<Integer> factors = new ArrayList<Integer>(); 
    for (int i = 2; i <= n; i++) { 
     while (n % i == 0) { 
     factors.add(i); 
     n /= i; 
     } 
    } 
    return factors; 
    }

來源

2015-03-31 15:56:13

你可以通過處理因子2作爲一個特殊情況，然後迭代奇數來加快速度。此外，不需要測試任何因素'我'哪裏'我*我> n';當在提供的代碼中遇到這種情況時，'n'是質數（最後一個因子）或零。 – 2015-03-31 16:11:25

沒有想過總是把它分成儘可能小的數字，所以它永遠不會達到非質數。謝謝！ – platelminto 2015-03-31 16:19:04

堅持你的一般算法，而不是重新寫你的primesBelow(..)方法：我會說：

一旦divides = true，你可以打出來的for循環
素數檢查的循環終止條件複雜可以減少到Math.sqrt(n) - 我不會通過數學，但你可以自己看看。提高代碼

來源

2015-03-31 16:01:56

一種方法是刪除您的IO循環結構中。也就是說，

static ArrayList<Integer> primeNumbersBelow(long n) { 
    ArrayList<Integer> ay = new ArrayList<Integer>(); 
    ay.add(2); 

    for(int i = 3; i < ((n % 2 != 0) ? (n + 1)/2 : n/2); i++) { 
     boolean divides = false; 
     for(int j = 2; j < i; j++) { 
      if(i % j == 0) { 
       divides = true; 
      } 
     } 
     if(!divides) { 
      ay.add(i); 
      //REMOVE THE FOLLOWING LINE 
      System.out.println(i); 
     } 
    } 
    return ay; 
}

我敢肯定，你會看到一個巨大的性能提升只是從一個人。

來源

2015-03-31 18:00:03

計算素數因子分解的更有效方法是什麼？

回答

相關問題