207 lines
4.7 KiB
Python
207 lines
4.7 KiB
Python
"""
|
||
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number
|
||
would be 1+2+3+4+5+6+7=28. The first ten terms would be:
|
||
|
||
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
|
||
|
||
Let us list the factors of the first seven triangle numbers:
|
||
|
||
1 : 1
|
||
3 : 1, 3
|
||
6 : 1, 2, 3, 6
|
||
10 : 1, 2, 5, 10
|
||
15 : 1, 3, 5, 15
|
||
21 : 1, 3, 7, 21
|
||
28 : 1, 2, 4, 7, 14, 28
|
||
|
||
We can see that 28 is the first triangle number to have over five divisors.
|
||
What is the value of the first triangle number to have over five hundred divisors?
|
||
|
||
NOTE：
|
||
|
||
-> in Math
|
||
解法的核心是找到所有质因数及对应的最大幂, 根据组合数学的方法估算因数数量
|
||
-> in Coding
|
||
循环遍历
|
||
"""
|
||
|
||
import math
|
||
import random
|
||
import time
|
||
from collections import Counter
|
||
from functools import reduce
|
||
from math import gcd
|
||
from typing import List
|
||
|
||
|
||
def timer(func):
|
||
def wrapper(*args, **kwargs):
|
||
start_time = time.time()
|
||
result = func(*args, **kwargs)
|
||
end_time = time.time()
|
||
print(f"Time taken: {end_time - start_time} seconds")
|
||
return result
|
||
|
||
return wrapper
|
||
|
||
|
||
def get_factors(n):
|
||
if n == 0:
|
||
raise ValueError("0 没有因数集合")
|
||
n = abs(n) # 处理负数
|
||
factors = set()
|
||
for i in range(1, int(math.isqrt(n)) + 1):
|
||
if n % i == 0:
|
||
factors.add(i)
|
||
factors.add(n // i)
|
||
return sorted(factors)
|
||
|
||
|
||
def get_triangle_number(n: int) -> int:
|
||
return n * (n + 1) // 2
|
||
|
||
|
||
@timer
|
||
def main_coding() -> None:
|
||
n = 1
|
||
while True:
|
||
triangle_number = get_triangle_number(n)
|
||
factors = get_factors(triangle_number)
|
||
if len(factors) > 500:
|
||
print(triangle_number)
|
||
break
|
||
n += 1
|
||
|
||
|
||
def is_probable_prime(n: int, trials: int = 20) -> bool:
|
||
"""Miller-Rabin素性测试（快速判断是否为质数）"""
|
||
if n < 2:
|
||
return False
|
||
if n in (2, 3):
|
||
return True
|
||
if n % 2 == 0:
|
||
return False
|
||
|
||
# 将 n-1 写成 d * 2^s 的形式
|
||
d = n - 1
|
||
s = 0
|
||
while d % 2 == 0:
|
||
d //= 2
|
||
s += 1
|
||
|
||
# 测试
|
||
for _ in range(trials):
|
||
a = random.randrange(2, n - 1)
|
||
x = pow(a, d, n)
|
||
if x == 1 or x == n - 1:
|
||
continue
|
||
for _ in range(s - 1):
|
||
x = pow(x, 2, n)
|
||
if x == n - 1:
|
||
break
|
||
else:
|
||
return False
|
||
return True
|
||
|
||
|
||
def pollards_rho(n: int, max_iter: int = 100000) -> int | None:
|
||
"""
|
||
Pollard's Rho 算法：返回n的一个非平凡因子
|
||
|
||
Args:
|
||
n: 待分解的合数
|
||
max_iter: 最大迭代次数防止无限循环
|
||
|
||
Returns:
|
||
n的一个因子（可能是质数也可能是合数）
|
||
若失败返回None
|
||
"""
|
||
|
||
if n % 2 == 0:
|
||
return 2
|
||
|
||
# 随机生成多项式 f(x) = x^2 + c (mod n)
|
||
c = random.randrange(1, n - 1)
|
||
|
||
def f(x):
|
||
return (pow(x, 2, n) + c) % n
|
||
|
||
# Floyd 判圈算法
|
||
x = random.randrange(2, n - 1)
|
||
y = x
|
||
d = 1
|
||
|
||
iter_count = 0
|
||
while d == 1 and iter_count < max_iter:
|
||
x = f(x) # 乌龟：走一步
|
||
y = f(f(y)) # 兔子：走两步
|
||
d = gcd(abs(x - y), n)
|
||
iter_count += 1
|
||
|
||
if d == n:
|
||
# 失败，尝试其他参数（递归或返回None）
|
||
return pollards_rho(n, max_iter) if max_iter > 1000 else None
|
||
|
||
return d
|
||
|
||
|
||
def factorize(n: int | None) -> List[int | None]:
|
||
"""
|
||
完整因数分解：递归分解所有质因数
|
||
|
||
Args:
|
||
n: 待分解的正整数
|
||
|
||
Returns:
|
||
质因数列表（可能含重复）
|
||
"""
|
||
if n == 1:
|
||
return []
|
||
if n is None:
|
||
return [None]
|
||
|
||
# 如果是质数，直接返回
|
||
if is_probable_prime(n):
|
||
return [n]
|
||
|
||
# 获取一个因子
|
||
factor = pollards_rho(n)
|
||
|
||
if factor is None:
|
||
return [None]
|
||
|
||
# 递归分解
|
||
return factorize(factor) + factorize(n // factor)
|
||
|
||
|
||
def get_prime_factors(n: int) -> dict[int | None, int]:
|
||
"""获取所有不重复的质因数"""
|
||
return dict(Counter(factorize(n)))
|
||
|
||
|
||
def zuheshu(tl: list[int]) -> int:
|
||
xt = [x + 1 for x in tl]
|
||
return reduce(lambda x, y: x * y, xt)
|
||
|
||
|
||
@timer
|
||
def main_math() -> None:
|
||
n = 1
|
||
while True:
|
||
tn = get_triangle_number(n)
|
||
factors = get_prime_factors(tn)
|
||
if factors == {}:
|
||
n += 1
|
||
continue
|
||
if zuheshu(list(factors.values())) > 500:
|
||
print(tn)
|
||
break
|
||
n += 1
|
||
|
||
|
||
if __name__ == "__main__":
|
||
print("暴力试算：")
|
||
main_coding()
|
||
print("质因数分解：")
|
||
main_math()
|