1175. Prime Arrangements

# 1175. Prime Arrangements#

## 题目 #

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`

## 题目大意 #

• 1 <= n <= 100

## 解题思路 #

• 给出一个数 n，要求在 1-n 这 n 个数中，素数在素数索引下标位置上的全排列个数。
• 由于这一题的 `n` 小于 100，所以可以用打表法。先把小于 100 个素数都打表打出来。然后对小于 n 的素数进行全排列，即 n！，然后再对剩下来的非素数进行全排列，即 (n-c)！。两个的乘积即为最终答案。

## 代码 #

``````
package leetcode

import "sort"

var primes = []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

func numPrimeArrangements(n int) int {
primeCount := sort.Search(25, func(i int) bool { return primes[i] > n })
return factorial(primeCount) * factorial(n-primeCount) % 1000000007
}

func factorial(n int) int {
if n == 1 || n == 0 {
return 1
}
return n * factorial(n-1) % 1000000007
}

``````

Sep 6, 2020