การจัดเรียงจำนวนเฉพาะ (Prime Arrangements) ใน Python

หาจำนวนวิธีจัดเรียง (permutations) ของ 1 ถึง n ให้จำนวนเฉพาะ (prime numbers) อยู่ที่ index ที่เป็นจำนวนเฉพาะ ผลลัพธ์อาจใหญ่ คืนค่า modulo 10⁹ + 7

ตัวอย่าง: n = 5 ผลลัพธ์ = 12 วิธี เช่น [1,2,5,4,3] ถูกต้อง แต่ [5,2,3,4,1] ผิด เพราะ 5 อยู่ index 1 (ไม่ใช่ prime)

ขั้นตอนการแก้ปัญหา

1. สร้างฟังก์ชัน getNum(n) หาจำนวนเฉพาะ ≤ n:
   • เตรียมลิสต์จำนวนเฉพาะ 2 ถึง 100
   • นับจำนวนเฉพาะที่ ≤ n
2. คำนวณ permutations:
   • x = จำนวนเฉพาะ ≤ n
   • p = 1, m = 10⁹ + 7
   • คูณ factorial(x) mod m
   • คูณ factorial(n-x) 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):
        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

วิธีแก้แบบ Pythonic (ใช้ math.factorial)

import math

def numPrimeArrangements(n):
    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)
    
    MOD = 10**9 + 7
    primes = count_primes(n)
    return (math.factorial(primes) * math.factorial(n - primes)) % MOD