Python 中的素数排列

pythonserver side programmingprogramming更新于 2025/11/4 4:28:17

我们必须找到 1 到 n 的排列数，因此素数被放在素数索引处。答案可能很大，返回答案对 10^9 + 7 取模。因此，如果 n = 5，则输出将为 12。因此将有 12 个排列。一个可能的排列是 [1,2,5,4,3]，一个无效的排列是 [5,2,3,4,1]，因为 5 位于索引 1，不是素数。

为了解决这个问题，我们将遵循以下步骤 −

定义一个名为 getNum 的方法，如下所示 −
prime := 从 2 到 100 的所有素数的列表
set i := 0
while i < 素数列表的长度
- if prime[i] > n，然后返回 i
- i := i + 1
返回素数的长度
实际问题将按如下方式解决
x := getNum(n), p := 1, m := 10^9 + 7
for i := x down to 0
- p := p * i
- p := p mod m
for i := n – x down to 0
- p := p * i
- p := p mod m
返回 p

示例

让我们看看下面的实现以便更好地理解 −

class Solution(object):
   def getNum(self,n):
      primes = [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]
      i = 0
      while i < len(primes):
         if primes[i]>n:
            return i
         i+=1
      return len(primes)
   def numPrimeArrangements(self, n):
      """
      :type n: int
      :rtype: int
      """
      x = self.getNum(n)
      p = 1
      m = 1000000000+7
      for i in range(x,0,-1):
         p*=i
         p%=m
      for i in range(n-x,0,-1):
         p*=i
         p%=m
      return p
ob1 = Solution()
print(ob1.numPrimeArrangements(100))