Pythonでのプライムアレンジメント

1からnまでの順列の数を見つける必要があるため、素数は素数インデックスに配置されます。答えは大きくなる可能性があり、10 ^ 9 + 7を法とする答えを返します。したがって、n =5の場合、出力は12になります。したがって、12の順列があります。 1つの可能な順列は[1,2,5,4,3]であり、1つの無効な順列は[5,2,3,4,1]です。これは、5が素数ではないインデックス1に配置されているためです。

これを解決するには、次の手順に従います-

• getNumという1つのメソッドを次のように定義します-
• prime：=2から100までのすべての素数のリスト
• set i：=0
• whilei<プライムリストの長さ
  • prime [i]> nの場合、iを返します
  • i：=i + 1
• プライムの長さを返す
• 実際の問題は次のように解決されます
• x：=getNum（n）、p：=1、m：=10 ^ 9 + 7
• for i：=xから0まで
  • p：=p * i
  • p：=p mod m
• for i：=n –xから0まで
  • p：=p * i
  • p：=p mod m
• return 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