1175. Prime Arrangements

Description

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

💡 Hint 1:
Solve the problem for prime numbers and composite numbers separately.

💡 Hint 2:
Multiply the number of permutations of prime numbers over prime indices with the number of permutations of composite numbers over composite indices.

💡 Hint 3:
The number of permutations equals the factorial.

Submitted Code

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        prime_nums = 0

        for num in range(1, n+1):
            if self.is_prime(num):
                prime_nums += 1
        
        permutations = math.factorial(prime_nums) * math.factorial(n-prime_nums)
        return permutations % (10**9 + 7)


    def is_prime(self, num: int) -> bool:
        if num <= 1:
            return False
        for i in range(2, int(math.sqrt(num))+1):
            if num % i == 0:
                return False
        return True

Runtime: 1 ms | Beats 27.72%
Memory: 17.28 MB | Beats 96.30%

1부터 n까지 숫자 모두를 소수인지 판별하기 때문에 속도가 상대적으로 느리게 나왔다.

Other Solutions

1st

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        primes = [True] * (n + 1)
        for prime in range(2, int(math.sqrt(n)) + 1):
            if primes[prime]:
                for composite in range(prime * prime, n + 1, prime):  # 소수의 배수들은 모두 소수
                    primes[composite] = False
        cnt = sum(primes[2:])                                         # 소수 개수 카운트
        return math.factorial(cnt) * math.factorial(n - cnt) % (10**9 + 7)

time complexity: 𝑂(𝑛*log(log𝑛))
space complexity: 𝑂(𝑛)

에라토스테네스의 체 방법을 사용하면 소수를 훨씬 빠르게 찾을 수 있다.