当前位置:网站首页>LeetCode:1175. Prime permutation
LeetCode:1175. Prime permutation
2022-07-07 01:24:00 【Vicky__ three thousand and twenty-one】
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
边栏推荐
- C # method of calculating lunar calendar date 2022
- golang中的WaitGroup实现原理
- Niuke cold training camp 6B (Freund has no green name level)
- How to manage distributed teams?
- pyflink的安装和测试
- The cost of returning tables in MySQL
- Meet in the middle
- Realize incremental data synchronization between MySQL and ES
- 【js】获取当前时间的前后n天或前后n个月(时分秒年月日都可)
- 7.6 simulation summary
猜你喜欢
Lldp compatible CDP function configuration
[hfctf2020]babyupload session parsing engine
405 method not allowed appears when the third party jumps to the website
Dynamic planning idea "from getting started to giving up"
Let's see through the network i/o model from beginning to end
【C语言进阶篇】指针的8道笔试题
AI 从代码中自动生成注释文档
Can the system hibernation file be deleted? How to delete the system hibernation file
2022 Google CTF segfault Labyrinth WP
"Exquisite store manager" youth entrepreneurship incubation camp - the first phase of Shunde market has been successfully completed!
随机推荐
实现mysql与ES的增量数据同步
Maidong Internet won the bid of Beijing life insurance to boost customers' brand value
「笔记」折半搜索(Meet in the Middle)
Docker method to install MySQL
Neon Optimization: performance optimization FAQ QA
THREE. AxesHelper is not a constructor
机器学习:随机梯度下降(SGD)与梯度下降(GD)的区别与代码实现。
C language - array
JTAG principle of arm bare board debugging
Openjudge noi 1.7 10: simple password
Boot - Prometheus push gateway use
ARM裸板调试之JTAG原理
golang中的atomic,以及CAS操作
LeetCode:1175. 质数排列
gnet: 一个轻量级且高性能的 Go 网络框架 使用笔记
Lldp compatible CDP function configuration
AI 从代码中自动生成注释文档
HMM 笔记
1123. 最深叶节点的最近公共祖先
如何管理分布式团队?