Python的主要安排

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

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

• 定义一个称为getNum的方法，如下所示-

• 素数：=所有素数从2到100的列表

• 设置我：= 0

• 而我<主要列表的长度

• 如果prime [i]> n，则返回i

• 我：=我+ 1

• 素数的返回长度

• 实际问题将解决如下

• x：= getNum(n)，p：= 1，m：= 10 ^ 9 + 7

• 对于我：= x降至0

• p：= p *我

• p：= p mod m

• 对于i：= n – x降至0

• p：= p *我

• 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))

输入项

100

输出结果

682289015