Python 中的素數排列

我們需要找到 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 的所有素數的列表
• 設定 i := 0
• 當 i < prime 列表的長度時
  • 如果 prime[i] > n，則返回 i
  • i := i + 1
• 返回 prime 的長度
• 實際問題將按如下方式解決
• x := getNum(n), p := 1, m := 10^9 + 7
• 對於 i := x 到 0
  • p := p * i
  • p := p mod m
• 對於 i := n – x 到 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))

輸入

100

輸出

682289015

Arnab Chakraborty

更新於: 2020年4月29日

267 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習