Leetcode Link: 1175. 质数排列 - 力扣（LeetCode）
题目
请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。
让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
解法一
思路： 实际上就是质数只放在质数索引的位置，合数放在合数索引的位置。
这样，最终就是两个排列的乘积 所有质数的排列情况数x所有合数排列情况组合
由于题目n<100，所以可以打表提前把质数都写出来。
题解：
class Solution:
def numPrimeArrangements(self, n: int) -> int:
# 所有质数打表，最后一个要超过100，否则99无法找到质数的数量
all_100 = [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,101]
# 找到小于n的所有质数的数量
for i, val in enumerate(all_100):
if n < val:
nums_zhi = i
break
nums_he = n - i
res = (self.jiecheng(nums_zhi) * self.jiecheng(nums_he)) % (10**9+7)
return res
# 排列组合数
def jiecheng(self, m):
ans = 1
while(m>1):
ans *= m
m -= 1
return ans