投影Euler#37可截断素数

Question

可截断数字定义如下： 3797这个数字有一个有趣的特性。作为素数本身，可以从左到右连续删除数字，并在每个阶段保持素数：3797、797、97和7。类似地，我们可以从右到左工作：3797、379、37和3。你知道吗

求从左到右和从右到左都可以截断的十一个素数之和。你知道吗

注：2、3、5和7不被认为是可截断素数。你知道吗

def is_prime(number):
    """returns True for a prime number, False otherwise."""
    factor = 2
    while factor * factor <= number:
        if number % factor == 0:
            return False
        factor += 1
    return True


def get_truncatable(n):
    """returns truncatable numbers within range n."""
    for number in range(9, n, 2):
        if is_prime(number):
            check = 0
            for index in range(-1, -len(str(number)), -1):
                less_right = str(number)[:index]
                if not is_prime(int(less_right)):
                    check += 1
            if check == 0:
                for index in range(1, len(str(number))):
                    less_left = str(number)[index:]
                    if not is_prime(int(less_left)):
                        check += 1
                if check == 0:
                    yield number


if __name__ == '__main__':
    print((list(get_truncatable(1000000))))

代码应该返回[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]或它们的等价和：748317

它返回：[11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 197, 311, 313, 317, 373, 797, 1373, 1997, 3137, 3797, 7331, 73331, 739397]

正如你所看到的，我的代码中的'31'和所有其他数字一样是可截断的，当我搜索时，我发现代码给出了第一个输出。你知道吗

这种差异究竟来自何方？我错了吗？我说得对吗？你知道吗

Answer 1

更有效的方法是生成一组素数作为字符串。然后检查列表中是否有符合截断条件的条目（用子字符串更容易表示）：

首先生成高达1000000的字符串素数。有很多种方法可以做到这一点，但埃拉托斯特尼的筛子简单而快速：

R      = 1000000
sieve  = [True]*R
primes = set()
for n in range(2,R+1):
    if sieve[n-1]:
        primes.add(str(n))
        sieve[n*n-1::n] = [False]*len(range(n*n-1,R,n))

然后检查合格的素数：

truncable = []
for p in primes:
    if len(p) == 1: continue
    if all(p[:i] in primes and p[i:] in primes for i in range(1,len(p))):
        truncable.append(int(p))

print(sum(truncable))

Answer 2

对于1，您的is_prime返回True。你可以把它作为一个特例。你知道吗

def is_prime(number):
    """returns True for a prime number, False otherwise."""
    factor = 2
    while factor * factor <= number:
        if number % factor == 0:
            return False
        # additional speedup here
        factor += 1 + factor % 2
    return number > 1