题目133：考察哪个质数永远无法证整除长度为10^n的循环整数
本帖最后由 永恒的蓝色梦想 于 2020-6-28 08:40 编辑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(10n).
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(10n) 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(10n).
Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).
题目：
如果一个数全部由 1 组成，称之为一个循环整数。定义 R(k) 为长度为 k 的循环整数，例如 R(6) = 111111。
让我们考虑形如 R(10n) 的循环整。
尽管 R(10)，R(100)，和 R(1000) 都无法被 17 整除，但是 R(10000) 可以。但是不存在 n 使得 R(10n) 能够被 19 整除。事实上，在 100 以下的质数中只有 11，17，41 和 73 这四个能够成为某个 R(10n) 的因子。
求 100000 以下不能整除任何 R(10n) 的质数的和。
抛砖引玉。
import time
import math
t0 = time.time()
MAXPRIME = 100000
max2, max5 = int(math.log(MAXPRIME, 2)), int(math.log(MAXPRIME, 5)) # 2的最高次幂和5的最高次幂
MAXN = int(math.pow(10, max(max2, max5)))
ISPRIME = *MAXPRIME
ISPRIME = ISPRIME = False
for i in range(2, MAXPRIME//2):
if ISPRIME == False:
continue
for j in range(i*i, MAXPRIME, i):
ISPRIME = False
count, sum = 3, 10 # 10^n一定不能整除2、3和5，不参与循环，计入初始值。
for p in range(7, MAXPRIME, 2):
if ISPRIME:
if pow(10, MAXN, 9*p) != 1:
count += 1
sum += p
# print(, end='\t')
print("Answer: ", sum)
print("Running time: ", time.time()-t0, "s")
Answer:453647705
Running time:0.10031580924987793 s
页:
[1]