概念釐清
- 因數 (Factor/Divisor)： 能整除給定整數 n 的正整數。如 12 的因數：1,2,3,4,6,12。
- 質因數 (Prime Factor)： 既是因數又是質數的數。質因數分解將 n 表示為質數乘積：
12 = 2^2 × 3^1，100 = 2^2 × 5^2。 - 互質 (Coprime)： 兩數最大公約數為 1。如 15 和 16 互質。
試除法求質因數分解 (適合 n ≤ 10^12)
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <math.h>
void prime_factorize(uint64_t n) {
printf("%" PRIu64 " = ", n);
bool first = true;
for (uint64_t p = 2; p * p <= n; ++p) {
if (n % p == 0) {
int cnt = 0;
while (n % p == 0) {
n /= p;
++cnt;
}
if (!first) printf(" × ");
first = false;
printf("%" PRIu64, p);
if (cnt > 1) printf("^%d", cnt);
}
}
if (n > 1) { // 剩餘為大質數
if (!first) printf(" × ");
printf("%" PRIu64, n);
}
printf("\n");
}
int main() {
prime_factorize(1); // 1 =
prime_factorize(12); // 12 = 2^2 × 3
prime_factorize(97); // 97 = 97
prime_factorize(1000000007ULL); // 質數
prime_factorize(18446744073709551615ULL); // 2^64-1 = 3×5×17×257×641×65537×6700417
return 0;
}
複雜度與優化
- 試除法時間複雜度
O(√n)，對 64 位整數最坈 ~4×10^9 次迴圈，需優化。 - 優化 1：預先篩選質數表 (埃氏篩/線性篩) 至 10^6，僅試除質數，減少 90% 迴圈。
- 優化 2：Pollard's Rho + Miller-Rabin 確定性測試 (64 位基數 {2,325,9375,28178,450775,9780504,1795265022})，期望
O(n^{1/4})，毫秒級分解 64 位合數。 - 優化 3：預計算小質數乘積 (Primorial) 快速排除小因子。
應用場景
- RSA 密鑰生成/破解 (大整數分解)。
- 約數個數/和計算：
d(n) = ∏(ei+1), σ(n) = ∏(p_i^{e_i+1}-1)/(p_i-1)。 - 歐拉函數
φ(n) = n ∏(1-1/p_i)。 - 中國剩餘定理 (CRT) 模數分解。
