0041 全数字素数
* * * *
拉格朗日计划
* * * *
全数字素数

若一个n位数中1到n每个数字恰好出现了一次,则称该数为全数字数。例如2143就是一个四位的全数字数,同时它也是素数。

最大的全数字素数是几?

本题难度:



解答

注意到$1+\ldots+9=45$以及$1+\ldots+8=36$,因此八位和九位的全数字数都能被3整除,所以全数字素数最多只有七位。

先用筛法生成$10^4$以内的素数,再生成数字1到7的全排列,取其中最大的素数即得结果$7652413$。

import itertools

target=10000
d=[0]*target
n=2
while n < target:
    for i in range(n+n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1
p=[k for k in range(2,target) if d[k]==0]

def isPrime(m):
    i=0
    while i < len(p) and p[i]*p[i]<=m and m%p[i]:
        i+=1
    return i>=len(p) or m%p[i]>0


print max(j for i in itertools.permutations("1234567") for j in [int("".join(i))] if isPrime(j))