题目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

很没有效率的暴力解法

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
[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