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

jerryxjr1220

1. """
   
2. R(k) = (10**k-1)/9
   
3. if R(k) mod p == 0, then 10**k mod 9p == 1.
   
4. """
   
5. primes=[True]*1000000
   
6. primes[:2]=[False]*2
   
7. for i,prime in enumerate(primes):
   
8.         if prime:
   
9.                 for j in range(i*i, 1000000, i):
   
10.                         primes[j]=False
    
11. count = 0
    
12. s = 0
    
13. for k,trueprime in enumerate(primes):
    
14.         if trueprime:
    
15.                 if pow(10,10**9,9*k) == 1:
    
16.                         count += 1
    
17.                         s += k
    
18.         if count == 40:
    
19.                 print(s)
    
20.                 break

复制代码

843296