[LeetCode] 1175. Prime Arrangements

😎풀이

1. 1부터 n까지 소수의 수를 확인
2. 소수의 수를 통해 얻을 수 있는 경우의 수 계산
3. 소수가 아닌 수를 통해 얻을 수 있는 경우의 수 계산
4. 두 경우의 수를 곱하여 최종 경우의 수 확인
5. 10^9 + 7를 통해 결괏값의 나머지를 반환

const MOD_BIGINT = 1_000_000_007n;

function numPrimeArrangements(n: number): number {
    const primeCount = countPrime(n);
    const remainCount = n - primeCount;

    const result = (factorial(primeCount) * factorial(remainCount)) % MOD_BIGINT;
    
    return Number(result);
};

function countPrime(n: number): number {
    if (n < 2) return 0;
    const primes = new Array(n + 1).fill(true);
    primes[0] = primes[1] = false;

    for (let i = 2; i * i <= n; i++) {
        if (primes[i]) {
            for (let j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }

    return primes.filter(Boolean).length;
}

function factorial(n: number): bigint {
    let result = 1n;
    for (let i = 2; i <= n; i++) {
        result = (result * BigInt(i)) % MOD_BIGINT;
    }
    return result;
}