问题
我们称一个n位数是泛数字，是因为它上面从1至n都只出现一次。例如，2143就是一个4位泛数字，而且它是一个素数。
那么，存在的最大的n位泛数字素数是多少？
* 传送门
分析
既要判断泛数字、又要判断素数，还要越大越好，泛数字最大可以有9位，泛数字只是正整数的一小部分，但却要遍历所有——这显得暴力解题很不合理，即使使用筛选法生成9位内的素数也显得太浪费内存。
那么就从另外一个角度出发——是否可以直接生成泛数字？答案肯定是可以的，这个只是排列组合的问题。这样至少可以把候选搜索空间减少。
但9位以内的泛数字，全部排列出来有9!+8!+7!+6!+5!+4!+3!+2!+1!这么多个，素数判定还是那个问题——即便用筛选法也显得太浪费内存。
这个题目里面藏着很重要的线索以便继续简化。首先观察9位泛数字，各位相加之和为1+2+…+9=45。而45又可以被3整除，这说明整段9位泛数字都不可能是素数——它们肯定可以被3整除！
同理还可以发现，8、6、5、3、2位泛数字都有这种情况！1位的情况就只有1本身，1不是素数。
所以，可能存在素数的就只有4位和7位泛数字！缩减到这么小的搜索空间，即便直接用试除法判断素数也不显得昂贵了。
刚开始就被这个题目蒙骗了，害我写了个n位内所有泛数字的生成器……发现这个规律后，就要另外再写n位泛数字生成器……
答案
// answer: after analysis
const start = Date.now()
function to_number(digits) {
let num = 0
const last = digits.length - 1
for (let i = last; i >= 0; --i)
num += digits[last - i] * Math.pow(10, i)
return num
}
function swap(digits, i, j) {
[digits[i], digits[j]] = [digits[j], digits[i]]
}
function* permutation(digits, from, to) {
if (to > 1) {
if (from == to)
yield to_number(digits)
else
for (let i = from; i <= to; ++i) {
swap(digits, from, i)
for (let num of permutation(digits, from + 1, to))
yield num
swap(digits, i, from)
}
}
}
function* pandigital(n) { // 只输出n位的泛数字
const digits = []
for (let i = n; i > 0; --i)
digits.push(i)
for (let num of permutation(digits, 0, digits.length - 1))
yield num
}
function* permutation_all(digits, selected = []) {
if (selected.length > 0)
yield to_number(selected)
for (let i = 0; i < digits.length; ++i) {
const digits_copy = digits.slice()
const selected_copy = selected.slice()
selected_copy.push(digits_copy.splice(i, 1)[0])
for (let num of permutation_all(digits_copy, selected_copy))
yield num
}
}
function* pandigital_within(n) { // 输出小于等于n位的泛数字
const digits = []
for (let i = n; i > 0; --i)
digits.push(i)
for (let num of permutation_all(digits))
yield num
}
function isPrime(n) {
if (n == 2 || n == 3 || n == 5 || n == 7)
return true
else if (n < 2)
return false
if ((n % 2) == 0)
return false
const end = Math.sqrt(n)
for (let i = 3; i <= end; i += 2)
if ((n % i) == 0)
return false
return true
}
let result = 0
for (let num of pandigital(7))
if (isPrime(num) && num > result)
result = num
if (result == 0)
for (let num of pandigital(4))
if (isPrime(num) && num > result)
result = num
alert(result + ', ' + (Date.now() - start) + 'ms')
