LeetCode：1175. Prime permutation

subject ：
1175. Permutation of prime numbers

Please help me to 1 To n Number design arrangement scheme , Make all of 「 Prime number 」 Should be placed in 「 Prime index 」（ Index from 1 Start ） On ; You need to return the total number of possible solutions .

Let's review 「 Prime number 」： The prime number must be greater than 1 Of , And it cannot be expressed by the product of two positive integers less than it .

Because the answer could be big , So please return to the answer model mod 10^9 + 7 Then the result is .

 Example  1：

 Input ：n = 5
 Output ：12
 explain ： for instance ,[1,2,5,4,3]  Is an effective arrangement , but  [5,2,3,4,1]  No , Because in the second case, prime numbers  5  It is wrongly placed in the index as  1  Location .
 Example  2：

 Input ：n = 100
 Output ：682289015

Tips ：

• 1 <= n <= 100

analysis ：
n by 1 or 2 when , The return value is 1. When n Greater than 2 when , Determine whether the number is a prime number by traversing and dividing , If a number can be divisible i, that i As composite .

Code ：

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        count1 = 1  #  Combined number 
        count2 = 1  #  Prime quantity 
        ans = 1
        if n == 1 or n == 2:
            return 1
        for i in range(3, n+1):
            for j in range(2, i):
                if i % j == 0:
                    count1 += 1
                    ans = ans * count1 % (7 + 10**9)
                    break
            else:
                count2 += 1
                ans = ans * count2 % (7 + 10**9)
        return ans