如何糾正我的素數分解程序？

Question

這裏是我輸出給定數字的素因式分解的程序。我仍然只是一個初學者，所以我知道它不是最有效的代碼。當我輸入相對較大的數字時會出現問題。

輸入：11輸出：11

輸入：40輸出：2 2 2 5

輸入：5427輸出：3 3 3 3 67

輸入：435843輸出：3 3 79 613

輸入：23456789輸出：無（有似乎是一個無限循環的代碼應該返回23456789，因爲它本身就是一個素數）

什麼可能CAUS這個問題？

import java.util.Scanner; 

public class PrimeFactorization { 
    public static boolean isPrime(long n) { 
     boolean boo = false; 
     long counter = 0; 
     if (n == 1) { 
      boo = false; 
     } else if (n == 2) { 
      boo = true; 
     } else { 
      for (long i = 2; i < n; i++) { 
       if (n % i == 0) { 
        counter++; 
       } 
      } 
      if (counter == 0) { 
       boo = true; 
      } 
     } 
     return boo; 
    } 

    public static void primeFactorization(long num) { 
     for (long j = 1; j <= num; j++) { 
      if (isPrime(j)) { 
       if (num % j == 0) { 
        while (num % j == 0) { 
         System.out.printf(j + " "); 
         num = num/j; 
        } 
       } 
      } 
      if (num == 1) { 
       break; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     System.out.println("Enter any number:"); 
     long num = scanner.nextLong(); 
     System.out.print("Prime factorization of your number is: "); 
     primeFactorization(num); 
     scanner.close(); 
    } 
} 

Answer 1

無論代碼有多高效，分解大數字需要一段時間 - 只要它可能感覺計算機已掛起。考慮到你的代碼，即使是大量的數據也需要很長時間。

您可以做的主要事情是提高代碼的效率，以便注意對於任何一對數字因素，其中一個因子的數量不會超過數字的平方根。您可以使用這個事實來限制循環，以減少O（n）到O（log n）的算法順序。

long sqrt = Math.sqrt(number); 

for (long i = 2; i < sqrt; i++) { 
    ... 

還有很多其他的事情可以做，但是這個改變會產生最大的影響。

如果在循環過程number變化值（例如在你的第二個上分解循環），你當然如果需要重新計算終值：

for (...) 
    // if number changes 
    sqrt = Math.sqrt(number); 

Answer 2

沒有實際的錯誤 - 你只是在做一個非常低效的方法。基本上，你在檢查每個數字之間的1和23456789之間的首要性，在分裂之前。

這樣做是完全沒有意義的。當你從1到23456789工作時，每當你發現一個因素時，你就知道它必須是素數，因爲你已經劃分了所有較小的因子。因此，如果您執行以下所有操作，則此功能仍能正常工作，而且速度更快。

• 徹底刪除isPrime方法。
• 取出線if (isPrime(j)) {，並且匹配}
• 改變環路以便j開始於2，像for(long j = 2 ; j <= num ; j++) {
• 從迴路的末端刪除if (num == 1) { break; }。它根本沒有任何用處。