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

हमें 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
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))

इनपुट

आउटपुट

682289015