题目132:求一个非常大的循环整数的前40个质数因子
Large repunit factorsA number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k.
For example, R(10) = 1111111111 = 11×41×271×9091, and the sum of these prime factors is 9414.
Find the sum of the first forty prime factors of R(109).
题目:
一个全部由 1 组成的数字叫做循环整数。定义 R(k) 为一个长度为 k 的循环整数。
例如, R(10) = 1111111111 = 11×41×271×9091,这几个质数因子之和为 9414。
求 R(109) 的前 40 个质数因子之和。
"""
R(k) = (10**k-1)/9
if R(k) mod p == 0, then 10**k mod 9p == 1.
"""
primes=*1000000
primes[:2]=*2
for i,prime in enumerate(primes):
if prime:
for j in range(i*i, 1000000, i):
primes=False
count = 0
s = 0
for k,trueprime in enumerate(primes):
if trueprime:
if pow(10,10**9,9*k) == 1:
count += 1
s += k
if count == 40:
print(s)
break
843296
页:
[1]