1175.质数排列

链接：1175.质数排列
难度：Easy
标签：数学
简介：请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。

题解 1 - typescript

• 编辑时间：2021-12-04
• 执行用时：88ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：算出质数位置进行阶乘。

function numPrimeArrangements(n: number): number {
  const MOD = BigInt(10 ** 9 + 7);
  const cnt = count(n);
  return Number((factorial(cnt) * factorial(n - cnt)) % MOD);
  function count(n: number): number {
    const arr: boolean[] = new Array(n + 1).fill(true);
    arr[0] = arr[1] = false;
    for (let i = 2; i <= n; i++) {
      if (!arr[i]) continue;
      for (let j = 2; i * j <= n; j++) arr[i * j] = false;
    }
    return arr.filter(Boolean).length;
  }
  function factorial(n: number): bigint {
    let ans = 1n;
    for (let i = 2n; i <= n; i++) ans = (ans * i) % MOD;
    return ans;
  }
}