MediumRating 1500
2507. Smallest Value After Replacing With Sum of Prime Factors
mathsimulationnumber-theory
解題說明
Smallest Value After Replacing With Sum of Prime Factors
題目描述： 給定正整數 n，每次操作可以將 n 替換為其所有質因數之和。重複此操作直到 n 不再改變，返回最終的 n。
解題思路： 直接模擬：每次將 n 分解質因數，計算質因數之和，用這個和替換 n。重複直到 n 不再改變（n 本身是質數時就停止了，因為質數的質因數之和就是自己）。
質因數分解：從 2 開始，嘗試整除 n，每次除盡後累加該質因數。處理完所有 <= sqrt(n) 的因數後，若 n > 1 則 n 本身是質因數。
C++ 解法
複雜度分析
時間複雜度：O(sqrt(n) * log n) — 每次質因數分解 O(sqrt(n))，最多重複 O(log n) 次（值每次至少減半或不變）
空間複雜度：O(1) — 只用常數空間
虛擬碼
1. Loop: a. Factorize n: for each prime factor p, add p to sum (with multiplicity) b. If sum == n, return n (fixed point reached) c. Set n = sum 2. Factorization: try divisors from 2 to sqrt(n) - While d divides n: sum += d, n /= d - If n > 1 after loop: sum += n (remaining prime factor)
其他解法
-
預計算質數表法：先用篩法建出小於 sqrt(n) 的質數表，分解時只嘗試質數。常數更小但 n <= 10^5 時差異不大。
-
最小質因數篩（SPF Sieve）：預處理每個數的最小質因數。分解時直接查表除以最小質因數。適合需要大量分解的場景，單次分解 O(log n)。
延伸思考
- 如果操作改為「替換為質因數之積除以質因數個數」，收斂行為會如何改變？
- 從 2 到 n 的所有數，哪些數經過一次操作後就不變了？有什麼規律？
- 如果要計算到達最終值所需的操作次數，最壞情況是多少次？