嵇爾的吐槽

#没事画轮子的嵇尔不定期的(W)碎(E)碎(B)念(B)和(L)吐(O)槽(G)

Problem 60 Prime pair sets 2019-06-27 08:30:00

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

这个花了很长时间,主要是暴力破解的时候一会儿内存爆了,一会儿CPU爆了。

所以不要问我13和1237是怎么回事,都是magic number,最后结果出来还需要cancel。

之前有个7开始的结果,比13的这个还大。

import math
import sys
NOT_PRIME_LIST = []
PRIME_LIST = []
il = range(3, 20000)
IL_PRIME = []


def is_Prime(number):
    if number in PRIME_LIST:
        return True
    if number in NOT_PRIME_LIST:
        return False
    if number < 2:
        return False
    for x in range(2, int(math.sqrt(number)) + 1):
        if number % x == 0:
            NOT_PRIME_LIST.append(number)
            return False
    PRIME_LIST.append(number)
    return True


for i in il:
    if (is_Prime(i)):
        IL_PRIME.append(i)

print len(IL_PRIME)
print


def concat(a, b):
    return eval(str(a)+str(b))


def check_c(m, n):
    return is_Prime(concat(n, m)) and is_Prime(concat(m, n))


for a in IL_PRIME:
    if a < 13:
        continue
    for b in IL_PRIME:
        if b < 1237:
            continue
        if b <= a:
            continue
        if check_c(a, b):
            # print a, b
            for c in IL_PRIME:
                if c < b:
                    continue
                if check_c(b, c) and check_c(a, c):
                    # print a,b,c
                    for d in IL_PRIME:
                        if d < c:
                            continue
                        if check_c(a, d) and check_c(b, d) and check_c(c, d):
                            print a, b, c, d
                            for e in IL_PRIME:
                                if e < d:
                                    continue
                                if check_c(a, e) and check_c(b, e) and check_c(c, e) and check_c(d, e):
                                    print a, b, c, d, e
                                    print a+b+c+d+e
评论共