วิธีตรวจสอบจำนวนเฉพาะ (Prime Number) ใน Python หลายวิธี

บทความนี้สำรวจ 3 วิธีในการตรวจสอบจำนวนเฉพาะใน Python ตั้งแต่พื้นฐานไปสู่การเพิ่มประสิทธิภาพ

วิธีที่ 1: ตรวจสอบทุกตัว (Naive)

ตรวจสอบหารได้ทุกตัวจาก 2 ถึง n-1

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

print(f"Is 2 prime: {is_prime(2)}")  # True
print(f"Is 4 prime: {is_prime(4)}")  # False
print(f"Is 7 prime: {is_prime(7)}")  # True

วิธีที่ 2: ตรวจสอบถึง √n

ถ้ามีตัวหาร จะต้องมีคู่ที่ ≤ √n

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

วิธีที่ 3: ข้ามเลขคู่ (Optimized)

เลขคู่ > 2 ไม่เป็นเฉพาะ ตรวจสอบเฉพาะเลขคี่

import math

def is_prime(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

เปรียบเทียบประสิทธิภาพ

ขั้นสูง: สำหรับ n ใหญ่มาก ใช้ Miller-Rabin Primality Test (Probabilistic) O(k log³ n)