문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

1부터 n까지 소수가 소수 인덱스(1부터 시작)에 위치하는 순열의 개수를 반환해라.

Example

#1
Input: n = 5
Output: 12
Explanation: [1, 2, 5, 4, 3]은 유효한 순열이지만 [5, 2, 3, 4, 1]은 소수 5가 인덱스 1에 있기 때문에 유효하지 않다.

#2
Input: n = 100
Output: 682289015

Constraints

• 1 <= n <= 100

Solved

class Solution {
    public int numPrimeArrangements(int n) {
        int mod = (int) 1e9 + 7;
        int count = 0;

        for(int i = 2; i <= n; i++){
            if(isPrime(i)){
                count++;
            }
        }

        return (int) ((factorial(count, mod) * factorial(n - count, mod)) % mod);
    }

    private boolean isPrime(int n){
        for(int i = 2; i <= n / 2; i++){
            if(n % i == 0){
                return false;
            }
        }

        return true;
    }

    private long factorial(int n, long mod){
        long f = 1;

        for(int i = 2; i <= n; i++){
            f = (f * i) % mod;
        }

        return f;
    }
}