[LeetCode] 1175. Prime Arrangements 质数排列


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 modulo 10^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且只能被1和其本身整除的数。刚拿到题时,可能会被这里的全排列,质数坐标啥的所迷惑,并且疑惑地看着其 Easy 的标签,怀疑着人生。但其实这些都是障眼法,完全可以把质数和非质数分离开来,各个排列,比如有 cnt 个质数,那么其排列的方法总数就是 cnt 的阶乘(中学学过),同理,非质数的排列方法就是 n-cnt 的阶乘,然后把二者相乘就行了。所以这道题的难点还是求1到n中所有的质数的个数,这就跟之前那道 Count Primes 一样了。这里可以挨个检查 [1, n] 中的每个数字是否是质数,其实只需要要检测 [3, n] 中的所有奇数,因为除了2以外的质数一定是奇数。判定质数的最简单直接的方法,就是查找看其是否有非1非其本身的因子,这里可以从3开始检测,只需要检测到 sqrt(i) 就行了,而且只用检测奇因子,若是质数,则 cnt 自增1。最后分别计算 cnt 和 n-cnt 的阶乘,并相乘,别忘了对超大数取余,参见代码如下:


解法一:

class Solution {
public:
    int numPrimeArrangements(int n) {
        long res = 1, cnt = 1, M = 1e9 + 7;
        for (int i = 3; i <= n; i += 2) {
            bool pass = true;
            for (int factor = 3; factor * factor <= i; factor += 2) {
                if (i % factor == 0) {
                    pass = false;
                    break;
                }
            }
            if (pass) ++cnt;
        }
        for (int i = 1; i <= cnt; ++i) {
            res = res * i % M;
        }
        for (int i = 1; i <= n - cnt; ++i) {
            res = res * i % M;
        }
        return res;
    }
};

其实检测1到n中质数的个数更高效的方法是用 埃拉托斯特尼筛法 Sieve of Eratosthenes,在之前的 Count Primes 中也有讲解到。这里实际上就是快速标记所有不是质数的位置,然后剩下的就都是质数了,对于每个质数,其乘以另一个大于1的数字得到的数字肯定不是质数,只要其小于等于n,就标记为 false。其余部分跟上面的解法没有啥区别,参见代码如下:


解法二:

class Solution {
public:
    int numPrimeArrangements(int n) {
        long res = 1, cnt = 0, M = 1e9 + 7;
        vector<bool> prime(n + 1, true);
        prime[0] = false; prime[1] = false;
        for (int i = 2; i * i <= n; ++i) {
            if (prime[i]) {
                for (int factor = 2; factor * i <= n; ++factor) {
                    prime[factor * i] = false;
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (prime[i]) ++cnt;
        }
        for (int i = 1; i <= cnt; ++i) {
            res = res * i % M;
        }
        for (int i = 1; i <= n - cnt; ++i) {
            res = res * i % M;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1175


类似题目:

Count Primes


参考资料:

https://leetcode.com/problems/prime-arrangements/

https://leetcode.com/problems/prime-arrangements/discuss/371968/Detailed-Explanation-using-Sieve

https://leetcode.com/problems/prime-arrangements/discuss/371862/JavaPython-3-two-codes-each-count-only-primes-then-compute-factorials-for-both-w-analysis.


LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] 1175. Prime Arrangements 质数排列

上一篇:设计模式-单例模式


下一篇:C#之垃圾回收