1175.质数排列

1175.质数排列

Category	Difficulty	Likes	Dislikes
algorithms	Easy (49.15%)	45	-

Tags
Companies
请你帮忙给从 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

---

Discussion | Solution

思路

其实就是统计 n 以内数字素数的数量，例如 5 有 3 个素数：2、3、5，同时素数下标也是 2、3、5，对这些数进行全排列 A33，剩余的 1、4 进行全排列 A22。两个相乘就是最后的答案。在 JS 中大数乘法有精度问题，直接取余答案不准确，需要使用 bigint 类型进行计算。

解答

/*
 * @lc app=leetcode.cn id=1175 lang=javascript
 *
 * [1175] 质数排列
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var numPrimeArrangements = function (n) {
  let count = 0;

  const check = (num) => {
    for (let j = 2; j <= Math.sqrt(num); j++) {
      if (num % j === 0) {
        return false;
      }
    }
    return true;
  };

  for (let i = 2; i <= n; i++) {
    if (check(i)) count++;
  }

  const mod = BigInt(1e9 + 7);

  const calculate = (n) => {
    let res = BigInt(1),
      num = BigInt(n);
    while (num > 0) {
      res = (res * num--) % mod;
    }
    return res;
  };

  return +((calculate(n - count) * calculate(count)) % mod).toString();
};
// @lc code=end