日期：2026年4月15日
ZeroJudge 題目連結：d121. 00583 - Prime Factors
解題想法
因為 $n$ 的上限為 $2^{31}$，質因數的上限為 $\sqrt{2^{31}} \approx 46340$，可以先建 $1$ 到 $46340$ 的質數表，然後再用試除法找質因數。不過這題最麻煩的地方，反而是在於要拼出正確的輸出格式。
Python 程式碼
使用時間約為 39 ms，記憶體約為 9.1 MB，通過測試。
def solve():
import sys
# 建質數表，1 ~ sqrt(2^31)，大約 46340
maxn = 46340
sieve = [True]*(maxn + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(maxn**0.5) + 1):
if sieve[i]:
for j in range(i*i, maxn + 1, i):
sieve[j] = False
primes = [i for i in range(maxn + 1) if sieve[i]]
# 主要的解題過程
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
n = int(data[ptr])
ptr += 1
if n == 0: break # 停止運作的條件
if n == 1: # 特例
result.append("1 = 1\n")
continue
factors = [] # 質因數
m = n # n 的質先存到 m
if m < 0: # 負數
factors.append(-1) # 先加入 -1
m = -m # 轉為正值
# 找質因數，m 的值先存到 x
x = m
for p in primes:
if p*p > x: # 沒有更大的質因數，中止迴圈
break
while x%p == 0:
factors.append(p)
x //= p
if x > 1: factors.append(x)
# 組合答案
res = " x ".join(map(str, factors))
result.append(f"{n:d} = {res}\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
