当前位置:网站首页>LeetCode:1175. 质数排列
LeetCode:1175. 质数排列
2022-07-06 17:39:00 【Vicky__3021】
题目:
1175. 质数排列
请你帮忙给从 1 到 n 的数设计排列方案,使得所有的「质数」都应该被放在「质数索引」(索引从 1 开始)上;你需要返回可能的方案总数。
让我们一起来回顾一下「质数」:质数一定是大于 1 的,并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大,所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1:
输入:n = 5
输出:12
解释:举个例子,[1,2,5,4,3] 是一个有效的排列,但 [5,2,3,4,1] 不是,因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
示例 2:
输入:n = 100
输出:682289015
提示:
- 1 <= n <= 100
解析:
n为1或2时,返回值为1。当n大于2时,通过遍历整除判断该数是否为质数,如果某个数可以整除i,那么i为合数。
代码:
class Solution:
def numPrimeArrangements(self, n: int) -> int:
count1 = 1 # 合数数量
count2 = 1 # 质数数量
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
边栏推荐
- Js逆向——捅了【马蜂窝】的ob混淆与加速乐
- 405 method not allowed appears when the third party jumps to the website
- golang中的Mutex原理解析
- Force buckle 1037 Effective boomerang
- Dark horse notes - exception handling
- Let's see through the network i/o model from beginning to end
- 微信公众号发送模板消息
- 力扣1037. 有效的回旋镖
- ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
- Neon Optimization: performance optimization FAQ QA
猜你喜欢
随机推荐
golang中的WaitGroup实现原理
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
pyflink的安装和测试
Asset security issues or constraints on the development of the encryption industry, risk control + compliance has become the key to breaking the platform
mysql: error while loading shared libraries: libtinfo. so. 5: cannot open shared object file: No such
黑马笔记---创建不可变集合与Stream流
Let's see through the network i/o model from beginning to end
Data type of pytorch tensor
Grc: personal information protection law, personal privacy, corporate risk compliance governance
Taro applet enables wxml code compression
UI control telerik UI for WinForms new theme - vs2022 heuristic theme
动态规划思想《从入门到放弃》
如何管理分布式团队?
SuperSocket 1.6 创建一个简易的报文长度在头部的Socket服务器
Spark TPCDS Data Gen
UI控件Telerik UI for WinForms新主题——VS2022启发式主题
分享一个通用的so动态库的编译方法
线段树(SegmentTree)
405 method not allowed appears when the third party jumps to the website
Atomic in golang and CAS operations