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⁹ + 7.

• permutations [数]排列（permutation 的复数）

• modulo 模数

解法

方法一：质数判断+组合数学

求复合条件的方案数，使得所有质数都放在质数索引上，所有合数放在合数索引上，质数放置和合数放置是相互独立的，总的方案数即为【所有质数都放在质数索引上的方案数】*【所有合数都放在合数索引上的方案数】。求【所有质数都放在质数索引上的方案数】，即求质数个数numPrimes的阶乘。【所有合数都放在合数索引上的方案数】同理。求质数个数时，可以使用试除法。【204.计数质数的官方题解】列举了更多的求质数个数的方法，最后注意计算过程中需要对10⁹+7取模。

代码

package com.leetcode.question.medium;

/** * 1175 Prime Arrangements * * @ClassName PrimeArrangements1175 * @Author eistert * @Date 2022/7/1 18:01 **/
public class PrimeArrangements1175 {
    

    public static void main(String[] args) {
    

    }

    static final int MOD = 1000000007;


    public int numPrimeArrangements(int n) {
    
        int numPrimes = 0;

        for (int i = 1; i <= n; i++) {
    
            if (isPrime(i)) {
    
                numPrimes++;
            }
        }

        // 为什么质数放置和合数放置是相互独立的，总的方案数即为
        long total = factorial(numPrimes) * factorial(n - numPrimes);

        long totalMod = total % MOD;

        return (int) totalMod;
    }

    /** * 是否为质数 */
    public boolean isPrime(int n) {
    
        if (n == 1) {
    
            return false;
        }

        for (int i = 2; i * i <= n; i++) {
     // 为什么是i * i <= n
            if (n % i == 0) {
    
                return false;
            }
        }

        return true;
    }


    /** * 阶乘 */
    public long factorial(int n) {
    
        long res = 1;
        for (int i = 1; i <= n; i++) {
    
            res *= i;
            res %= MOD;
        }

        return res;
    }
}

转载

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/prime-arrangements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。