算法经典面试题 -- 质数排列（JS）
题目
请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。
让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1：
输入：n = 5 输出：12 解释：举个例子，[1,2,5,4,3] 是一个有效的排列， 但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。复制代码
示例 2：
输入：n = 100 输出：682289015复制代码
提示：
1 <= n <= 100
题解
首先我们需要理解题目。
题目本质上是排序方案计算总数，例如： n = 5 ，排序总数就是 5 * 4 * 3 * 2 * 1 。
但题目中提出质数必须在质数的位置，例如： n = 5 ，其中 2、3、5 是质数，也就是 2、3、5 只能在索引 2、3、5 的位置出现。
那么我们排序方案应该分为两种
质数的排列数量
非质数的排列数量
最后两数相乘取其值。
那么我们的代码思路应该如下：
计算出质数的个数
计算质数排序方案种类
计算非质数（总数 - 质数）方案种类
两者相乘取其值
计算出质数个数函数：
// 判断是否是质数
const isPrimeNumber = (n) => {
let cnt = 0
for (let i = 2; i < n; i++) {
if (n % i === 0) return false
}
return true
}
// 获取质数数量
const getPrimeNumberCnt = (n) => {
let cnt = 0
for (let i = 2; i <= n; i++) {
if (isPrimeNumber(i)) {
cnt++
}
}
return cnt
}
const primeNumberCnt = getPrimeNumberCnt(n)复制代码计算方案种类函数：
// 阶乘计算
const getFactorial = (n) => {
let factorial = 1
for (let i = 2; i <= n; i++) {
factorial *= i
}
return factorial
}复制代码计算质数排序方案种类：
// 质数排序数量 const pCnt = getFactorial(primeNumberCnt)复制代码
计算非质数拍寻方案种类：
// 非质数排序数量 const oCnt = getFactorial(n - primeNumberCnt)复制代码
计算总个数并取模：
const mod = 10**9 + 7 return (pCnt * oCnt) % mod复制代码
问题
由于众所周知的原因（最后会解释），JS 中 Number 的最大值是 2 ** 53 -1 ，超出该值会丢失精度，我们写的代码大概率是跑的起来但结果错误的。
解决该问题有两种方案：
使用
BigInt每次阶乘都
取模
使用 BigInt ：
// 阶乘计算
const getFactorial = (n) => {
let factorial = BigInt(1)
for (let i = 2; i <= n; i++) {
factorial *= BigInt(i)
}
return factorial
}
const pCnt = getFactorial(primeNumberCnt)
const oCnt = getFactorial(n - primeNumberCnt)
const MOD = BigInt(10**9 + 7)
return (pCnt * oCnt) % MOD复制代码每次阶乘都 取模 ：
const MOD = 10**9 + 7
const getFactorial = (base, n) => {
let factorial = base
for (let i = 2; i <= n; i++) {
factorial *= i
factorial = factorial % MOD
}
return factorial
}
const pCnt = getFactorial(1, primeNumberCnt)
const max = getFactorial(pCnt, n - primeNumberCnt)
return max % MOD复制代码方案无优劣，自行选取。
答案
/**
* @param {number} n
* @return {number}
*/
var numPrimeArrangements = function (n) {
var MOD = BigInt(10 ** 9 + 7)
// 判断是否是质数
const isPrimeNumber = (n) => {
let cnt = 0
for (let i = 2; i < n; i++) {
if (n % i === 0) return false
}
return true
}
// 获取质数数量
const getPrimeNumberCnt = (n) => {
let cnt = 0
for (let i = 2; i <= n; i++) {
if (isPrimeNumber(i)) {
cnt++
}
}
return cnt
}
// 阶乘计算
const getFactorial = (n) => {
let factorial = BigInt(1)
for (let i = 2; i <= n; i++) {
factorial *= BigInt(i)
}
return factorial
}
const primeNumberCnt = getPrimeNumberCnt(n)
const pCnt = getFactorial(primeNumberCnt)
const oCnt = getFactorial(n - primeNumberCnt)
return (pCnt * oCnt) % MOD
};复制代码解释
JS 中 Number 的最大值为什么是 2 ** 53 -1 ？
Number，遵循 IEEE 754 规范，采用双精度存储（double precision），占用 64 位，其中1位用来表示符号位，11位用来表示指数，剩下52位表示尾数，就是这个Number.MAX_SAFE_INTEGER，又称为最大安全数，其值为2^53 -1，大于 9007199254740992 的可能会丢失精度
数组的最大长度是2的32次方减1，这个不是指数组只能存2^32-1位数据，也不是说数组的下标最大值就是2^32-1，而是指数组的length属性最大值为2^32-1。
ECMAScript 标准约定number数字需要被当成 64 位双精度浮点数处理，但事实上，一直使用 64 位去存储任何数字实际是非常低效的，所以 JavaScript 引擎并不总会使用 64 位去存储数字，引擎会在内部采用其他内存表示方式，如 32 位。
取模为什么是 10 ** 9 + 7 ？
来源：知乎作者（EntropyIncreaser） 链接：www.zhihu.com/question/49…
其实不止1e9+7，还有1e9+9和998244353。这三个数都是一个质数，同时小于 。所以有什么好处呢？
所有模过之后的数在加法操作在int范围内不会溢出，即
。
在乘法操作后在long long范围内不会溢出，即
。
对于
中的整数，可进行mod P乘法群意义下的除法，即可以使用扩展欧几里得算法求得
中的a。
(另：其实也可以不mod一个质数，那样的话除法就复杂一些，需要进行素因子分解之后帮助除法和中国剩余定理来还原最终答案。)
作者：sincenir
链接：https://juejin.cn/post/7025900704782876708