题目146：考察一个质数模式

欧拉计划

Investigating a Prime Pattern

The smallest positive integer n for which the numbers n²+1, n²+3, n²+7, n²+9, n²+13, and n²+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?

题目：

使得 n²+1, n²+3, n²+7, n²+9, n²+13, 以及 n²+27 为连续质数的最小的正整数 n 为 10。100 万以下所有满足上述条件的 n 值之和是 1242490。

求 1 亿五千万以下所有满足上述条件的 n 值之和。

jerryxjr1220

很没有效率的暴力解法

1. def is_prime(n):
   
2.         if n<2: return False
   
3.         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):
   
4.                 if pow(p,n-1,n) != 1:
   
5.                         return False
   
6.         return True
   
7. 
   
8. def solve(limit):
   
9.         n = 0
   
10.         for i in range(1,limit//10):
    
11.                 t1 = 10*i
    
12.                 t2 = 10*i+2
    
13.                 t3 = 10*i+8
    
14.                 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):
    
15.                         n += t3
    
16.                         continue
    
17.                 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):
    
18.                         n += t2
    
19.                         continue
    
20.                 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):
    
21.                         n += t1
    
22.                         continue
    
23.         return n
    
24. print(solve(150000000))

复制代码

676333270
[Finished in 993.5s]

guosl

根据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