嵇爾的吐槽

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

Problem 37 Truncatable primes 2016-10-18 09:31:00

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.


可截素数

3797有着奇特的性质。不仅它本身是一个素数,而且如果从左往右逐一截去数字,剩下的仍然都是素数:3797、797、97和7;同样地,如果从右往左逐一截去数字,剩下的也依然都是素数:3797、379、37和3。

只有11个素数,无论从左往右还是从右往左逐一截去数字,剩下的仍然都是素数,求这些数的和。

注意:2、3、5和7不被视为可截素数。

import math


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


def get_children(number):
    result = [number]
    number_level = len(str(number))
    for i in range(1, number_level):
        result.append(eval(str(number)[i:]))
        result.append(eval(str(number)[:i]))
    return result

result = 0
for i in range(8, 739798):
    if is_Prime(i) and not '0' in str(i):
        ok = True
        numbers = get_children(i)
        for n in numbers:
            if not is_Prime(n):
                ok = False
                break
        if ok:
            print i
            result += i

print "result = %s" % result

上面一个是比较愚蠢的暴力破解方法,唯二的magic number就是8和739798,最初版本就是题目说了有11个素数嘛,就设了11循环,一开始其实算出来最大的是739397。

[Finished in 12.9s]

下面是这个快很多的一个方法,比较奇怪的就是2的问题,其他就用奇数来拼数字,至少少了一半的计算量

import math


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


def get_children(number):
    result = [number]
    number_level = len(str(number))
    for i in range(1, number_level):
        result.append(eval(str(number)[i:]))
        result.append(eval(str(number)[:i]))
    return result

line = []

for a in [1, 3, 5, 7, 9]:
    for b in [1, 3, 5, 7, 9]:
        line.append(eval("%s%s" % (b, a)))
        for c in [1, 3, 5, 7, 9]:
            line.append(eval("%s%s%s" % (c, b, a)))
            for d in [1, 3, 5, 7, 9]:
                line.append(eval("%s%s%s%s" % (d, c, b, a)))
                for e in [1, 3, 5, 7, 9]:
                    line.append(eval("%s%s%s%s%s" % (e, d, c, b, a)))
                    for f in [1, 3, 5, 7, 9]:
                        line.append(eval("%s%s%s%s%s%s" % (f, e, d, c, b, a)))
                    line.append(eval("%s%s%s%s%s" % (2, d, c, b, a)))
            line.append(eval("%s%s%s%s" % (2, c, b, a)))
        line.append(eval("%s%s%s" % (2, b, a)))
    line.append(eval("%s%s" % (2, a)))
result = 0
for i in line:
    if is_Prime(i):
        ok = True
        numbers = get_children(i)
        for n in numbers:
            if not is_Prime(n):
                ok = False
                break
        if ok:
            print i
            result += i

print "result = %s" % result

这个跑下来结果是:

[Finished in 1.2s]

至少还能接受是吧。

我觉得还能直接在素数末尾加数字来弄,应该可以快更多。

评论共