We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?
全数字素数
如果一个 n 位数恰好使用了 1 至 n 每个数字各一次,则称为全数字数。例如,2143 就是一个 4 位全数字数,同时它也是一个素数。
最大的全数字素数是多少?
一般来说题目给出的例子不会是最大的结果,因此我们可以从五位数开始。由于五位数的各位和为 15(三的倍数)故不可,六位数为 15 + 6 = 21 同样不行,七位数为 28,八位数为 36 不行,九位数为 45 不行。
综上,唯一可能的数字只有七位数了。对整个 1000000 到 9999999 遍历也用不了多少时间,不过既然还能优化最好还是不要这样做,如果这个数字为素数的话它的结尾只能是 1,3,7。这样我们需要检测的数字只有 3 * 6! = 2160 个了。
(defun eu41-gen (ls tail)
(cond
((null ls) `((,tail)))
(t (cl-loop
for a in ls append
(let ((res (eu41-gen (remove a ls) tail)))
(cl-loop
for b in res collect
(cons a b)))))))
(defun eu41-list2num (ls)
(cl-reduce (lambda (s a) (+ (* s 10) a)) ls))
(setq eu41-nums
(mapcar 'eu41-list2num
(append (eu41-gen '(1 2 3 4 5 6) 7)
(eu41-gen '(2 3 4 5 6 7) 1)
(eu41-gen '(1 2 4 5 6 7) 3))))
接着使用朴素素数判断方法即可:
(defun eu7-isprime (n)
(cond
((<= n 1) nil)
((< n 4) t)
((zerop (% n 2)) nil)
((< n 9) t)
((zerop (% n 3)) nil)
(t (let ((bound (floor (sqrt n))))
(named-let f ((i 5))
(cond
((> i bound) t)
((zerop (% n i)) nil)
((zerop (% n (+ i 2))) nil)
(t (f (+ i 6)))))))))
(nth 0 (sort (cl-remove-if-not 'eu7-isprime eu41-nums) '>))
=> 7652413