题目132：求一个非常大的循环整数的前40个质数因子

欧拉计划

Large repunit factors

A 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(10⁹).

题目：

一个全部由 1 组成的数字叫做循环整数。定义 R(k) 为一个长度为 k 的循环整数。

例如， R(10) = 1111111111 = 11×41×271×9091，这几个质数因子之和为 9414。

求 R(10⁹) 的前 40 个质数因子之和。

jerryxjr1220

"""
R(k) = (10**k-1)/9
if R(k) mod p == 0, then 10**k mod 9p == 1.
"""
primes=[True]*1000000
primes[:2]=[False]*2
for i,prime in enumerate(primes):
        if prime:
                for j in range(i*i, 1000000, i):
                        primes[j]=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