#55600: 大數值因數分解解法
0xseanlee
(0xseanlee)
import sys
import math
import random
# ==========================================
# 1. 數論基礎工具函式（代替 SymPy 內部工具）
# ==========================================
def isprime(n):
"""Miller-Rabin 質數檢定：秒殺大數質數判斷"""
if n < 2:
return False
if n in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
return True
if n % 2 == 0 or n % 3 == 0:
return False
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for a in bases:
if n <= a:
break
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
# ==========================================
# 2. SymPy 核心演算法重構（小因數試除 & Pollard's Rho）
# ==========================================
def _factorint_small(factors, n, limit=32768, fail_max=600):
"""快速試除小質數"""
for p in [2, 3]:
if n % p == 0:
count = 0
while n % p == 0:
count += 1
n //= p
factors[p] = factors.get(p, 0) + count
p = 5
w = 2
fails = 0
while p <= limit and p * p <= n:
if n % p == 0:
count = 0
while n % p == 0:
count += 1
n //= p
factors[p] = factors.get(p, 0) + count
fails = 0
else:
fails += 1
if fails >= fail_max:
break
p += w
w = 6 - w
return n, p
def pollard_rho(n, max_steps=10000):
"""Pollard's Rho 演算法，帶防卡死重試"""
if n % 2 == 0:
return 2
if isprime(n):
return n
for _ in range(10):
c = random.randint(1, n - 1)
x = random.randint(2, n - 1)
y = x
d = 1
steps = 0
while d == 1 and steps < max_steps:
x = (pow(x, 2, n) + c) % n
y = (pow(y, 2, n) + c) % n
y = (pow(y, 2, n) + c) % n
d = math.gcd(abs(x - y), n)
steps += 1
if 1 < d < n:
return d
return None
# ==========================================
# 3. 主函式：重現 SymPy factorint(n) 邏輯
# ==========================================
def factorint(n):
n = int(n)
if n < 0:
res = factorint(-n)
res[-1] = 1
return res
if n < 2:
return {}
if isprime(n):
return {n: 1}
factors = {}
# 階段 1：試除小質數
n, next_p = _factorint_small(factors, n)
if n == 1:
return factors
if isprime(n):
factors[n] = factors.get(n, 0) + 1
return factors
# 階段 2：大數使用 Pollard's Rho
def _factor_large(num):
if num == 1:
return
if isprime(num):
factors[num] = factors.get(num, 0) + 1
return
divisor = pollard_rho(num)
if divisor is None or divisor == num:
i = next_p
while i * i <= num:
if num % i == 0:
divisor = i
break
i += 2
else:
divisor = num
_factor_large(divisor)
_factor_large(num // divisor)
_factor_large(n)
return factors
# ==========================================
# 4. 執行區塊（改用 input()）
# ==========================================
def main():
try:
# 改用 input()，按 Enter 就會立刻執行！
raw_input = input("").strip()
if not raw_input:
return
n = int(raw_input)
fac_dict = factorint(n)
# 格式化輸出 2^2 * 5 格式
factors_list = []
for prime in sorted(fac_dict.keys()):
count = fac_dict[prime]
if count == 1:
factors_list.append(str(prime))
else:
factors_list.append(f"{prime}^{count}")
print(" * ".join(factors_list))
except (EOFError, ValueError):
pass
if __name__ == '__main__':
main()