题目133：考察哪个质数永远无法证整除长度为10^n的循环整数

欧拉计划

Repunit nonfactors

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(6) = 111111.

Let us consider repunits of the form R(10ⁿ).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10ⁿ) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10ⁿ).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10ⁿ).

题目：

如果一个数全部由 1 组成，称之为一个循环整数。定义 R(k) 为长度为 k 的循环整数，例如 R(6) = 111111。

让我们考虑形如 R(10ⁿ) 的循环整。

尽管 R(10)，R(100)，和 R(1000) 都无法被 17 整除，但是 R(10000) 可以。但是不存在 n 使得 R(10ⁿ) 能够被 19 整除。事实上，在 100 以下的质数中只有 11，17，41 和 73 这四个能够成为某个 R(10ⁿ) 的因子。

求 100000 以下不能整除任何 R(10ⁿ) 的质数的和。

l910607

抛砖引玉。

1. import time
   
2. import math
   
3. t0 = time.time()
   
4. 
   
5. 
   
6. MAXPRIME = 100000
   
7. max2, max5 = int(math.log(MAXPRIME, 2)), int(math.log(MAXPRIME, 5))   # 2的最高次幂和5的最高次幂
   
8. MAXN = int(math.pow(10, max(max2, max5)))
   
9. 
   
10. 
    
11. ISPRIME = [True]*MAXPRIME
    
12. ISPRIME[0] = ISPRIME[1] = False
    
13. for i in range(2, MAXPRIME//2):
    
14.     if ISPRIME[i] == False:
    
15.         continue
    
16.     for j in range(i*i, MAXPRIME, i):
    
17.         ISPRIME[j] = False
    
18. 
    
19. count, sum = 3, 10     # 10^n一定不能整除2、3和5，不参与循环，计入初始值。
    
20. for p in range(7, MAXPRIME, 2):
    
21.     if ISPRIME[p]:
    
22.         if pow(10, MAXN, 9*p) != 1:
    
23.             count += 1
    
24.             sum += p
    
25.             # print([count, p], end='\t')
    
26. 
    
27. 
    
28. print("Answer: ", sum)
    
29. print("Running time: ", time.time()-t0, "s")
    

复制代码

Answer:  453647705
Running time:  0.10031580924987793 s