पायथन में प्राइम अरेंजमेंट

हमें 1 से n के क्रमपरिवर्तन की संख्या ज्ञात करनी है, इसलिए अभाज्य संख्याओं को अभाज्य सूचकांकों पर रखा जाता है। उत्तर बड़े हो सकते हैं, उत्तर मॉड्यूल 10^9 + 7 लौटाएं। इसलिए यदि n =5 है, तो आउटपुट 12 होगा। तो 12 क्रमपरिवर्तन होंगे। एक संभावित क्रमपरिवर्तन [1,2,5,4,3] होगा, एक अमान्य क्रमपरिवर्तन [5,2,3,4,1] है क्योंकि 5 को सूचकांक 1 पर रखा गया है, जो अभाज्य नहीं है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• गेटनम नामक एक विधि को इस प्रकार परिभाषित करें -
• प्राइम:=2 से 100 तक सभी अभाज्य संख्याओं की सूची
• सेट मैं :=0
• जबकि मैं <प्राइम लिस्ट की लंबाई
  • अगर अभाज्य[i]> n, तो मैं वापस आ जाता हूं
  • i :=i + 1
• प्राइम की वापसी लंबाई
• वास्तविक समस्या का समाधान इस प्रकार किया जाएगा
• 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
• वापसी पी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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