要求出正整数 n 的所有質因數及其因數次數，我們可以遍歷所有小於等於 n 的質數，並使用之前提到的 FactorTimes 函數來計算每個質數的因數次數。如果質數的因數次數大於0，我們將其加入結果字串中。為了效率，實際上只需遍歷到 sqrt(n) 即可，因為任何大於 sqrt(n) 的因數都不可能成對出現（除非它們是相同的因數，即 n 是某個質數的平方）。
以下是實現 PrimeFactor 函數的程式碼，這裡將使用 Java 語言，並結合之前討論的 FactorTimes 函數：
java
Copy code
public class PrimeFactors {
// 假設 FactorTimes 函數已被定義
// 為了完整性，在此提供一個簡單的 FactorTimes 實現
public static int FactorTimes(int n, int p) {
if (n % p == 0) {
return 1 + FactorTimes(n / p, p);
} else {
return 0;
}
}
// PrimeFactor 函數求正整數 n 的質因數及其因數次數
public static String PrimeFactor(int n) {
StringBuilder result = new StringBuilder();
// 特殊情況處理
if (n <= 1) {
return String.valueOf(n);
}
// 假設 PrimeAry 陣列存在且包含所有需要的質數
int[] PrimeAry = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; // 示例
for (int p : PrimeAry) {
if (p * p > n) {
break;
}
int times = FactorTimes(n, p);
if (times > 0) {
n /= Math.pow(p, times); // 減少 n 以避免重複計算
result.append(p).append("^").append(times).append(" * ");
}
}
if (n > 1) { // 如果剩下的 n 是一個質數
result.append(n);
} else if (result.length() > 0) { // 移除最後的 " * "
result.delete(result.length() - 3, result.length());
}
return result.toString();
}
public static void main(String[] args) {
System.out.println(PrimeFactor(20)); // 應該回傳 "2^2 * 5"
System.out.println(PrimeFactor(72)); // 應該回傳 "2^3 * 3^2"
System.out.println(PrimeFactor(97)); // 應該回傳 "97"
}
}
這段程式碼首先構建了一個 StringBuilder 對象來存儲結果字串。然後，它遍歷一個質數陣列 PrimeAry（這裡假設 PrimeAry 包含了所有小於或等於 n 的質數）。對於陣列中的每個質數 p，它計算 n 包含質數 p 的因數次數。如果次數大於0，則將其格式化後加入結果字串中。
阿摩線上測驗
登入