『LeetCode』1175 质数排列

题目

1175. 质数排列

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

题解

【质数排列】简单模拟

模拟

质数只能放在质数位置，非质数只能放在非质数位置，只需分别统计出质数数量和非质数数量再计算重排列数量即可。

重排列数量是很基础的计算了：假设有 \(k\) 个盒子需要顺序放入 \(k\) 个不同小球，那么第一个盒子有 \(k\) 种选择，第二个盒子有 \(k - 1\) 种选择，以此类推，最后一个盒子只有 \(1\) 种选择，所以总的排列数为 \(k\times (k - 1) \times \cdots \times 1 = k!\)

至于统计 \([1, n]\) 范围内的质数，可以有很多数学方法，但这里 \(n\) 范围不大，逐个判断即可。

# Code language: Python
class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        mod = int(1e9+7)
        p, np = 0, 1

        def isprime(x):
            for i in range(2, x):
                if x % i == 0:
                    return False
                elif i * i > x:
                    return True
            return True
        
        for i in range(2, n + 1):
            if isprime(i):
                p += 1
            else:
                np += 1
        
        ans = 1
        for i in chain(range(1, p + 1), range(1, np + 1)):
            ans = (ans * i) % mod
        return ans

// Code language: Java
class Solution {
    public int numPrimeArrangements(int n) {
        int p = 0, np = 1;
        long ans = 1, mod = 1000000007;
        for (int i = 2; i <= n; ++i) {
            if (isprime(i)) ++p;
            else ++np;
        }
        for (int i = 2; i <= p; ++i) ans = (ans * i) % mod;
        for (int i = 2; i <= np; ++i) ans = (ans * i) % mod;
        return (int) ans;
    }

    boolean isprime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) return false;
        }
        return true;
    }
}

// Code language: C++
class Solution {
public:
    int numPrimeArrangements(int n) {
        int p = 0, np = 1;
        long ans = 1, mod = 1000000007;
        for (int i = 2; i <= n; ++i) {
            if (isprime(i)) ++p;
            else ++np;
        }
        for (int i = 2; i <= p; ++i) ans = (ans * i) % mod;
        for (int i = 2; i <= np; ++i) ans = (ans * i) % mod;
        return (int) ans;
    }

    bool isprime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) return false;
        }
        return true;
    }
};

// Code language: C#
public class Solution {
    public int NumPrimeArrangements(int n) {
        int p = 0, np = 1;
        long ans = 1, mod = 1000000007;
        for (int i = 2; i <= n; ++i) {
            if (isprime(i)) ++p;
            else ++np;
        }
        for (int i = 2; i <= p; ++i) ans = (ans * i) % mod;
        for (int i = 2; i <= np; ++i) ans = (ans * i) % mod;
        return (int) ans;
    }

    bool isprime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) return false;
        }
        return true;
    }
}

// Code language: JavaScript
/**
 * @param {number} n
 * @return {number}
 */
var numPrimeArrangements = function (n) {
    /**
     * 判断给定值是否是质数
     * @param {number} x 
     * @returns {number}
     */
    var isprime = function (x) {
        for (let i = 2; i * i <= x; ++i) {
            if (x % i == 0) return false;
        }
        return true;
    };

    let p = 0, np = 1;
    for (let i = 2; i <= n; ++i) {
        if (isprime(i)) ++p;
        else ++np;
    }
    var ans = 1;
    const mod = 1000000007;
    for (let i = 2; i <= p; ++i) ans = (ans * i) % mod;
    for (let i = 2; i <= np; ++i) ans = (ans * i) % mod;
    return ans;
};

时间复杂度: \(O(n \sqrt{n})\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1175 质数排列

题目

标签

题解

模拟