পাইথনে প্রাইম এরেঞ্জমেন্ট (Prime Arrangements in Python)

সমস্যা বিবরণ

১ থেকে n পর্যন্ত সংখ্যাগুলোর পারমুটেশন বের করতে হবে যাতে প্রাইম সংখ্যাগুলো প্রাইম ইনডেক্সে রাখা হয়। উত্তর বড় হতে পারে, তাই ১০⁹ + ৭ দিয়ে মডুলো ফেরত দিন।

উদাহরণ: n = 5 → আউটপুট ১২। একটি বৈধ পারমুটেশন: [1,2,5,4,3]। অবৈধ: [5,2,3,4,1] (৫ ইনডেক্স ১-এ যা প্রাইম নয়)।

সমাধানের পদ্ধতি

1. n পর্যন্ত প্রাইম সংখ্যা কতটいる কাউন্ট করুন (getNum ফাংশন)।
2. প্রাইম সংখ্যা = x, নন-প্রাইম সংখ্যা = n - x।
3. উত্তর = (x! × (n-x)!) mod (10⁹+৭) ।
4. প্রাইম ইনডেক্সে প্রাইম সংখ্যা বসানোর x! ভাব, নন-প্রাইম ইনডেক্সে নন-প্রাইম বসানোর (n-x)! ভাব।

পাইথন উদাহরণ

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):
        x = self.getNum(n)
        p = 1
        m = 1000000007
        for i in range(x, 0, -1):
            p = (p * i) % m
        for i in range(n - x, 0, -1):
            p = (p * i) % m
        return p

ob1 = Solution()
print(ob1.numPrimeArrangements(100))

ইনপুট

100

আউটপুট

682289015

অপ্টিমাইজড ভার্সন (Sieve + Factorial)

import math

def count_primes(n):
    if n < 2: return 0
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, n+1, i):
                sieve[j] = False
    return sum(sieve)

def numPrimeArrangements(n):
    MOD = 10**9 + 7
    primes = count_primes(n)
    return (math.factorial(primes) * math.factorial(n - primes)) % MOD