Python: วิธีการหาเฉพาะจำนวน (Prime Number) และการเปรียบเทียบประสิทธิภาพ

การตรวจสอบเฉพาะจำนวน (Primality Test) เป็นปัญหาคลาสสิกใน Computer Science บทความนี้เปรียบเทียบ 3 อัลกอริทึมหลักและ Benchmark ประสิทธิภาพ

นิยาม

Prime Number (เฉพาะจำนวน) = จำนวนเต็มบวกที่มากกว่า 1 และหารด้วย 1 และตัวมันเองลงตัวเท่านั้น

อัลกอริทึมที่ 1: Trial Division - ตรวจสอบทุกตัวหาร (Naive)

Time Complexity: O(n)

def is_prime_naive(n):
    """ตรวจสอบโดยการหารทุกตัวตั้งแต่ 2 ถึง n-1"""
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

อัลกอริทึมที่ 2: Trial Division จนถึง √n (Optimized)

Time Complexity: O(√n) - เนื่องจากถ้า n = a×b แล้ว a ≤ √n หรือ b ≤ √n

import math

def is_prime_sqrt(n):
    """ตรวจสอบจนถึง Square Root"""
    if n <= 1:
        return False
    if n <= 3:
        return True  # 2, 3 are prime
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # Check only 6k ± 1 pattern (Optimization)
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

อัลกอริทึมที่ 3: Sieve of Eratosthenes (หาเฉพาะจำนวนทั้งหมดจนถึง N)

Time Complexity: O(n log log n) - เร็วที่สุดสำหรับการหา Prime ทั้งช่วง

def sieve_of_eratosthenes(limit):
    """หาเฉพาะจำนวนทั้งหมด ≤ limit"""
    if limit < 2:
        return []
    
    # Boolean Array: True = Prime Candidate
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            # Mark multiples of i as non-prime
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    
    # Collect Primes
    return [i for i, prime in enumerate(is_prime) if prime]

# ทดสอบ
primes = sieve_of_eratosthenes(100)
print(f"Primes up to 100: {primes}")
print(f"Count: {len(primes)}")  # 25

Optimized Sieve: Bit Array / Bytearray

def sieve_optimized(limit):
    """Memory Efficient Sieve using Bytearray"""
    if limit < 2:
        return []
    
    # Only odd numbers: index i represents number 2*i + 1
    sieve = bytearray(b'\x01') * ((limit // 2) + 1)
    sieve[0] = 0  # 1 is not prime
    
    for i in range(3, int(limit**0.5) + 1, 2):
        if sieve[i // 2]:
            # Mark odd multiples: i*i, i*i+2i, i*i+4i, ...
            sieve[i*i // 2 :: i] = b'\x00' * len(sieve[i*i // 2 :: i])
    
    primes = [2] + [2*i + 1 for i in range(1, len(sieve)) if sieve[i]]
    return primes

Probabilistic Primality Test: Miller-Rabin (สำหรับเลขใหญ่มาก)

import random

def is_prime_miller_rabin(n, k=10):
    """Miller-Rabin Primality Test (Probabilistic)"""
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False
    
    # Write n-1 = d * 2^s
    s = 0
    d = n - 1
    while d % 2 == 0:
        d //= 2
        s += 1
    
    # Witness Loop
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# Test Large Numbers
print(is_prime_miller_rabin(2**31 - 1))  # True (Mersenne Prime)
print(is_prime_miller_rabin(2**31))      # False

Performance Benchmark

import timeit
import math

def count_primes_naive(limit):
    return sum(1 for i in range(2, limit+1) if is_prime_naive(i))

def count_primes_sqrt(limit):
    return sum(1 for i in range(2, limit+1) if is_prime_sqrt(i))

def count_primes_sieve(limit):
    return len(sieve_of_eratosthenes(limit))

# Benchmark
limits = [1000, 5000, 10000]
methods = {
    "Naive O(n)": "count_primes_naive",
    "Sqrt O(√n)": "count_primes_sqrt",
    "Sieve O(n log log n)": "count_primes_sieve",
}

for limit in limits:
    print(f"\n=== Limit: {limit} ===")
    for name, func_name in methods.items():
        if name == "Naive O(n)" and limit > 5000:
            print(f"{name:25}: SKIP (Too Slow)")
            continue
        time = timeit.timeit(f"{func_name}({limit})", globals=globals(), number=1)
        print(f"{name:25}: {time:.4f}s")

ผลลัพธ์ Benchmark (ประมาณ)

=== Limit: 1000 ===
Naive O(n)                  : 0.0450s
Sqrt O(√n)                  : 0.0012s
Sieve O(n log log n)        : 0.0003s

=== Limit: 5000 ===
Naive O(n)                  : SKIP (Too Slow)
Sqrt O(√n)                  : 0.0085s
Sieve O(n log log n)        : 0.0012s

=== Limit: 10000 ===
Naive O(n)                  : SKIP (Too Slow)
Sqrt O(√n)                  : 0.0250s
Sieve O(n log log n)        : 0.0025s

Python Built-in: sympy.isprime()

# pip install sympy
from sympy import isprime, primerange, primepi

print(isprime(2**31 - 1))           # True
print(list(primerange(1, 50)))      # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
print(primepi(100))                 # 25 (Prime Counting Function π(x))

สรุป: เลือกอัลกอริทึมไหนดี?