1175. 质数排列

🟢   🔖  数学  🔗 力扣 LeetCode

题目

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo10^9 + 7.

Example 1:

Input: n = 5

Output: 12

Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100

Output: 682289015

Constraints:

• 1 <= n <= 100

题目大意

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

解题思路

1. 判断素数：

   • 定义一个 isPrime 函数，用来判断一个数字是否为素数。
   • 具体判断方法是：遍历从 2 到 sqrt(n) 的所有数，若 n 可以被其中的任何一个数整除，则 n 不是素数。

2. 素数和非素数的计数：

   • 使用 primes 变量来记录 1 到 n 之间的素数的数量。
   • 通过遍历从 1 到 n，调用 isPrime 函数判断每个数是否为素数。如果是素数，则 primes 加 1。

3. 非素数的数量：

   • 非素数的数量可以通过 nonPrimes = n - primes 来得到，因为 n 是从 1 到 n 的整数序列，除了素数外，其余的都是非素数。

4. 计算结果：

   • 素数的排列方式是 primes!，非素数的排列方式是 nonPrimes!。
   • 将 primes! 和 nonPrimes! 计算出来，并用模 10^9 + 7 对结果进行取模。

5. 返回结果：

   • 最终返回的结果是 primes! * nonPrimes! % (10^9 + 7)。

复杂度分析

• 时间复杂度：O(n * sqrt(n))

  • isPrime 函数的时间复杂度为 O(sqrt(n))。
  • 对每个数都调用一次，因此计算素数个数的时间复杂度为 O(n * sqrt(n))。

• 空间复杂度：O(1)，使用了常数空间来存储中间结果。

代码

/**
 * @param {number} n
 * @return {number}
 */
var numPrimeArrangements = function (n) {
	const mod = 10 ** 9 + 7;

	// 判断是否为质数
	const isPrime = (n) => {
		for (let i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) return false;
		}
		return n > 1;
	};

	let primes = 0, // 素数个数
		nonPrimes = 0; // 非素数个数
	let res = 1;

	// 素数和非素数的排列数相乘
	for (let i = 1; i <= n; i++) {
		if (isPrime(i)) {
			primes++;
			res *= primes;
		} else {
			nonPrimes++;
			res *= nonPrimes;
		}
		res %= mod;
	}
	return res;
};