Prime Arrangements — LeetCode 1175 Python Solution

The problem

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

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.

Python solution

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        def count(n):
            cnt = 0
            primes = [True] * (n + 1)
            for i in range(2, n + 1):
                if primes[i]:
                    cnt += 1
                    for j in range(i + i, n + 1, i):
                        primes[j] = False
            return cnt

        cnt = count(n)
        ans = factorial(cnt) * factorial(n - cnt)
        return ans % (10**9 + 7)

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1175. Prime Arrangements is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems