题目146：考察一个质数模式
Investigating a Prime PatternThe smallest positive integer n for which the numbers n2+1, n2+3, n2+7, n2+9, n2+13, and n2+27 are consecutive primes is 10. The sum of all such integers n below one-million is 1242490.
What is the sum of all such integers n below 150 million?
题目：
使得 n2+1, n2+3, n2+7, n2+9, n2+13, 以及 n2+27 为连续质数的最小的正整数 n 为 10。100 万以下所有满足上述条件的 n 值之和是 1242490。
求 1 亿五千万以下所有满足上述条件的 n 值之和。 很没有效率的暴力解法{:10_319:}
def is_prime(n):
if n<2: return False
for p in (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97):
if pow(p,n-1,n) != 1:
return False
return True
def solve(limit):
n = 0
for i in range(1,limit//10):
t1 = 10*i
t2 = 10*i+2
t3 = 10*i+8
if is_prime(t3*t3+1) and is_prime(t3*t3+3) and is_prime(t3*t3+7) and is_prime(t3*t3+9) and is_prime(t3*t3+13) and is_prime(t3*t3+27) and not is_prime(t3*t3+19) and not is_prime(t3*t3+21):
n += t3
continue
if is_prime(t2*t2+1) and is_prime(t2*t2+3) and is_prime(t2*t2+7) and is_prime(t2*t2+9) and is_prime(t2*t2+13) and is_prime(t2*t2+27) and not is_prime(t2*t2+19) and not is_prime(t2*t2+21):
n += t2
continue
if is_prime(t1*t1+1) and is_prime(t1*t1+3) and is_prime(t1*t1+7) and is_prime(t1*t1+9) and is_prime(t1*t1+13) and is_prime(t1*t1+27) and not is_prime(t1*t1+19) and not is_prime(t1*t1+21):
n += t1
continue
return n
print(solve(150000000))
676333270
根据n^2 + 1是素数所以n一定是偶数，所以：n = 0 mod 2.
由于n^2 + 3 是素数所以：n = 1,2 mod 3.
如果n=1 mod 5,则n^2 + 1是一个偶数，不行！
如果n=2 mod 5 则n^1+1是5的倍数，不行！
如果n=3 mod 5 则n^2+1是10的倍数，不行！
如果n=4 mod 5 则n^2 + 9是5的倍数，不行！
所以n=0 mod 5 故n一定是10的倍数。
如果n=0 mod 7 则n^2 + 7是7的倍数，不行！
如果n=1 mod 7 则n^2 + 13是7的倍数，不行！
如果n=2 mod 7 则n^2 + 3是7的倍数，不行！
如果n=5 mod 7 则n^2 + 3是7的倍数，不行！
如果n=6 mod 7 则n^2 + 13是7的倍数，不行！
所以n除7余数只能是3或4。
答案：676333270
页:
[1]