[leetcode] 1175. Prime Arrangements

[leetcode] 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 = 5Output: 12Explanation: 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 = 100Output: 682289015

Constraints:

1 <= n <= 100

分析

题目的意思是：求出质数排列，其中质数只能出现在质数的位置上。思路也很直接，求出给定n下的所有质数，其中质数只能放在质数的位置上，其他的位置放非质数，就是一个排列组合问题A(k)*A(n-k),其中A表示全排列，k表示质数的个数啦。

如果加上质数只能是奇数，那么在遍历求质数的时候可以进一步缩小遍历空间，这个可以留给读者实现，比较简单。

代码

class Solution: def isPrime(self,num): for i in range(1,int(sqrt(num))): k=i+1 if(num%k==0): return False return True def numPrimeArrangements(self, n: int) -> int: cnt=0 for i in range(n): if(i>0 and self.isPrime(i+1)): cnt+=1 res=1 for i in range(cnt): res=res*(i+1)%(10**9+7) for i in range(n-cnt): res=res*(i+1)%(10**9+7) return res

参考文献

​​LeetCode.1175-质数排列(Prime Arrangements)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。