041. 全数字素数(pandigital prime)

当一个N位数的数字各个数位分别使用了1至N所有的数字,我们就说这是一个N位的全数字。例如,2143是一个四位的全数字,同时还是一个素数。求最大的同时为素数和N位全数字的数。

分析:小学的时候我们都已经学过,当一个数字的所有数位之和是三的倍数,则这个数可以被三整除,因此不可能是一个素数。我们可以试着计算所有两位数以上的全数字各位数之和:

$$ \begin{aligned} 1+2&=3\\ 1+2+3&=6\\ 1+2+3+4&=10\\ 1+2+3+4+5&=15\\ 1+2+3+4+5+6&=21\\ 1+2+3+4+5+6+7&=28\\ 1+2+3+4+5+6+7+8&=36\\ 1+2+3+4+5+6+7+8+9&=45 \end{aligned} $$

我们可以很明显看到,只有四位和七位全数字的各位数之和不是三的倍数,因此只有这两个数位的全数字中可能存在素数。考虑到七位数必然大于四位数,所以我们从最大的七位全数字7654321开始筛选,依次寻找一个更小的素数,然后判断这个素数是否为全数字。判断的方法是检查该数字对应的字符串构成的集合是否等于由字符串1234567构成的集合,如果等于则是一个全数字,如果不等于就不是。我们首先在七位数的范围内寻找满足要求的数,如果找不到,再在四位数范围内寻找。经过尝试,我们在七位数的范围内就能找到,所以无需再在四位数范围内寻找。

from sympy import prevprime

def main():
    start = 7654321
    while True:
        prevp = prevprime(start)
        if set(str(prevp)) == set('1234567'):
            return prevp
        else:
            start = prevp