Easy

题目描述

返回 1 到 n 的排列中，质数位于质数索引位置（1 索引）的排列数量。

（回想一下，当且仅当一个整数大于 1，且不能写成两个小于它的正整数的乘积时，该整数是质数。）

由于答案可能很大，请返回答案模 10^9 + 7 的结果。

示例 1：

输入：n = 5
输出：12
解释：例如 [1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第 1 个位置上是质数 5。

示例 2：

输入：n = 100
输出：682289015

提示：

  • 1 <= n <= 100

提示：

  • 分别解决质数和合数的问题。
  • 将质数在质数索引上的排列数与合数在合数索引上的排列数相乘。
  • 排列数等于阶乘。

解题思路

解题思路

这道题的核心是理解排列规则：质数必须放在质数索引位置，合数（包括1）必须放在合数索引位置。

分析步骤：

  1. 找出规律：由于质数只能放在质数索引位置，合数只能放在合数索引位置，所以问题可以分解为两个独立的排列问题。

  2. 计算质数个数：统计 1 到 n 中质数的个数，记为 primeCount。

  3. 计算索引中的质数个数：统计 1 到 n 的索引中质数索引的个数，这与步骤2的结果相同。

  4. 分别计算排列数：

    • 质数在质数位置的排列数：primeCount!
    • 合数在合数位置的排列数：(n - primeCount)!

  5. 最终答案：两个排列数的乘积，即 primeCount! × (n - primeCount)!

实现要点：

  • 使用埃拉托斯特尼筛法或简单试除法判断质数
  • 计算阶乘时注意取模运算
  • 由于 n ≤ 100，可以直接计算阶乘

时间复杂度主要来自质数判断和阶乘计算，整体效率很高。

代码实现

class Solution {
public:
    int numPrimeArrangements(int n) {
        const int MOD = 1000000007;
        
        // 判断是否为质数
        auto isPrime = [](int num) {
            if (num <= 1) return false;
            if (num == 2) return true;
            if (num % 2 == 0) return false;
            for (int i = 3; i * i <= num; i += 2) {
                if (num % i == 0) return false;
            }
            return true;
        };
        
        // 计算阶乘
        auto factorial = [&](int num) {
            long long result = 1;
            for (int i = 2; i <= num; i++) {
                result = (result * i) % MOD;
            }
            return (int)result;
        };
        
        // 统计质数个数
        int primeCount = 0;
        for (int i = 1; i <= n; i++) {
            if (isPrime(i)) primeCount++;
        }
        
        // 计算排列数
        int primeArrangements = factorial(primeCount);
        int compositeArrangements = factorial(n - primeCount);
        
        return (1LL * primeArrangements * compositeArrangements) % MOD;
    }
};

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        MOD = 10**9 + 7
        
        def is_prime(num):
            if num <= 1:
                return False
            if num == 2:
                return True
            if num % 2 == 0:
                return False
            for i in range(3, int(num**0.5) + 1, 2):
                if num % i == 0:
                    return False
            return True
        
        def factorial(num):
            result = 1
            for i in range(2, num + 1):
                result = (result * i) % MOD
            return result
        
        # 统计质数个数
        prime_count = sum(1 for i in range(1, n + 1) if is_prime(i))
        
        # 计算排列数
        prime_arrangements = factorial(prime_count)
        composite_arrangements = factorial(n - prime_count)
        
        return (prime_arrangements * composite_arrangements) % MOD

public class Solution {
    public int NumPrimeArrangements(int n) {
        const int MOD = 1000000007;
        
        bool IsPrime(int num) {
            if (num <= 1) return false;
            if (num == 2) return true;
            if (num % 2 == 0) return false;
            for (int i = 3; i * i <= num; i += 2) {
                if (num % i == 0) return false;
            }
            return true;
        }
        
        long Factorial(int num) {
            long result = 1;
            for (int i = 2; i <= num; i++) {
                result = (result * i) % MOD;
            }
            return result;
        }
        
        // 统计质数个数
        int primeCount = 0;
        for (int i = 1; i <= n; i++) {
            if (IsPrime(i)) primeCount++;
        }
        
        // 计算排列数
        long primeArrangements = Factorial(primeCount);
        long compositeArrangements = Factorial(n - primeCount);
        
        return (int)((primeArrangements * compositeArrangements) % MOD);
    }
}

var numPrimeArrangements = function(n) {
    const MOD = 1000000007;
    
    function isPrime(num) {
        if (num < 2) return false;
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true;
    }
    
    function factorial(num) {
        let result = 1;
        for (let i = 2; i <= num; i++) {
            result = (result * i) % MOD;
        }
        return result;
    }
    
    let primeCount = 0;
    for (let i = 1; i <= n; i++) {
        if (isPrime(i)) primeCount++;
    }
    
    let nonPrimeCount = n - primeCount;
    
    return (factorial(primeCount) * factorial(nonPrimeCount)) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n√n)
空间复杂度O(1)

说明：

  • 时间复杂度：需要判断1到n中每个数是否为质数，每次判断的复杂度为O(√n)，总体为O(n√n)；计算阶乘的复杂度为O(n)
  • 空间复杂度：只使用了常数额外空间