leetcode-1175-easy

leetcode-1175-easy

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

思路一：分阶段处理，判断数字是否质数，组合公式计算，n 个数字里面有 m 个质数，质数都要放在质数位置，这样有 m!*(n-m)! 种排列方式

public int numPrimeArrangements(int n) {
    int primeCount = 0;
    for (int i = 1; i <= n; i++) {
        if (isPrime(i)) primeCount++;
    }

    long ans = 1;
    for (int i = 1; i <= primeCount; i++) {
        ans *= i;

        ans %= 1000000007;
    }
    for (int i = 1; i <= n - primeCount; i++) {
        ans *= i;

        ans %= 1000000007;
    }

    return (int)ans;
}

public boolean isPrime(int x) {
    if (x == 1 || x % 2 == 0 && x != 2) {
        return false;
    } else {
        for (int i = 2; i < x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
    }
    return true;
}