給定 n (≤ 10⁹)，求 1~n 中與 n 互質的正整數個數。即計算 φ(n)。多測試用例，n=0 結束。
若 n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ，則：
φ(n) = n · Π (1 - 1/pᵢ) = Π pᵢ^(aᵢ-1) · (pᵢ - 1)
#include
#include
int phi(int n) {
int res = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) res = res / n * (n - 1); // 剩餘質因子
return res;
}
int main() {
int n;
while (scanf("%d", &n) == 1 && n) {
printf("%d\n", phi(n));
}
return 0;
}
| 場景 | 推薦方法 | 理由 |
|---|---|---|
| 單次/少量查詢，n 大 | O(√n) 試除 | 無預處理開銷 |
| 大量查詢，n ≤ 10⁶/10⁷ | 線性篩預計算 φ | O(1) 查詢，總時間更優 |
| 大量查詢，n ≤ 10⁹ | 預計算質數表 + 試除 | 質數表加速分解 |
