037. 可截短素数(truncatable primes)

数字3797有一个有趣的性质:它自己是一个素数,同时我们可以从左至右逐步截断这个数字,得到3797,797,97和7,它们也都是素数。同样,我们也可以从右至左逐步截断这个数字,得到3797,379,37和3也都是素数。求仅有的十一个从左至右和从右至左都可以截短的素数之和(注:2,3,5和7不被认为是可截短素数)。

分析:题目已经说明2,3,5,7不是可截短素数,所以我们只需要对10以上的素数进行判断。首先我们需要编写一个判断某数学是否是双边可截短素数的函数,按从左到右以及从右到左的顺序依次截短某个数字,并判断截短后的数字是否是素数,如果不是,则返回假;如果所有截短数字都是素数,则满足双边可截短数的条件,返回真。

题目并没有给出双边可截短素数的上界,只说了只有十一个这样的数字,但为筛选特定范围的素数,我们仍然需要一个上界,这个上界需要保证我们能产生所有十一个双边可截短素数。经过尝试,一百万是一个符合要求的上界,因此我们可以据此生成从十到一百万的所有素数。对于两位数的素数,我们直接调用上面编写的函数判断其是否为双边可截短素数。对于三位数以上的素数,我们还可以发现一些条件能缩小筛选的范围,提高筛选的速度。

首先,由于可截短素数最后都会截短到只剩一位数,则三位及以上的可截短素数的首位和末尾数字必须是素数,又由于末尾是二或者五的数字必可以被二或五整除,所以为了保证每次截短后的数必然是素数,则首位和末尾数字只能是三或者七。其次,同样为了保证截短的数为数字,数字中的所有数位都不能有偶数以及五,因此只能出现一、三、七、九这四个数字。从数学角度说,这要求各数位数字构成的集合是集合{1,3,7,9}的一个子集。通过以上条件,我们可以将待筛选素数的范围从七万多降低两百多,大大减小了筛选范围。在判断满足以上两个条件后,我们再用上面的函数来检测数字是否是双边可截短素数。如果是,则对计数值累加一,同时对求和值进行累加,当计数值达到十一后,我们停止循环,并返回最后的求和值,即为所求。

对于可截短数字更完整系统的介绍可以参见维基百科

from sympy import isprime,sieve

def is_twoside_truncatable_prime(x):
    s = str(x)
    for i in range(1,len(s)):
        if not isprime(int(s[i:])) or not isprime(int(s[:i])):
            return False
    return True

def main():
    num,ans = 0,0
    for i in sieve.primerange(10,1e6):
        if i < 100 and is_twoside_truncatable_prime(i):
            num += 1
            ans += i
        elif i>=100:
            s = str(i)
            cond1 = (s[0]=='3' or '7') and (s[-1]=='3' or '7')
            cond2 = set(s)<={'1','3','7','9'}
            if cond1 and cond2 and is_twoside_truncatable_prime(i):
                num += 1
                ans += i
        if num>=11:
            return ans