Leetcode-1175. Prime Arrangements

subject

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 [ Count ] array （permutation Complex number ）

• modulo modulus

solution

Method 1 ： Prime number judgment + Combinatorial mathematics

Number of schemes for finding composite conditions , So that all prime numbers are placed on the prime index , All composite numbers are placed on the composite index , Prime number placement and composite number placement are independent of each other , The total number of schemes is 【 The number of schemes in which all prime numbers are placed on the prime index 】*【 The number of schemes in which all composite numbers are placed on the composite index 】. seek 【 The number of schemes in which all prime numbers are placed on the prime index 】, That is, find the number of prime numbers numPrimes The factorial .【 The number of schemes in which all composite numbers are placed on the composite index 】 Empathy . When finding the number of primes , You can use trial division .【204. Official solution of counting prime numbers 】 Enumerate more methods of finding the number of prime numbers , Finally, pay attention to the need for 10⁹+7 modulus .

Code

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++;
            }
        }

        //  Why are prime number placement and composite number placement independent of each other , The total number of schemes is 
        long total = factorial(numPrimes) * factorial(n - numPrimes);

        long totalMod = total % MOD;

        return (int) totalMod;
    }

    /** *  Is it a prime number  */
    public boolean isPrime(int n) {
    
        if (n == 1) {
    
            return false;
        }

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

        return true;
    }


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

        return res;
    }
}

Reprint

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/prime-arrangements
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .