ตรวจสอบจำนวนเฉพาะ (Prime Number) ใน Python

โจทย์: ตรวจสอบว่าตัวเลขที่กำหนดเป็นจำนวนเฉพาะหรือไม่

นิยาม

จำนวนเฉพาะ = จำนวนเต็มบวก > 1 ที่มีตัวหารได้แค่ 1 และตัวมันเอง (2, 3, 5, 7, 11, ...)

อัลกอริทึม

1. n ≤ 1 → ไม่ใช่เฉพาะ
2. ตรวจสอบหารได้จาก 2 ถึง n//2 (หรือ √n เพื่อประสิทธิภาพ)
3. ถ้าหารได้ตัวไหน → ไม่ใช่เฉพาะ
4. ไม่หารได้ทุกตัว → เป็นเฉพาะ

ตัวอย่างโค้ด Python

num = 17

if num > 1:
    for i in range(2, num // 2 + 1):
        if (num % i) == 0:
            print(num, "is not a prime number")
            break
    else:
        print(num, "is a prime number")
else:
    print(num, "is not a prime number")

ผลลัพธ์

17 is a prime number

เวอร์ชันฟังก์ชันที่ใช้ซ้ำได้

import math

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

# ทดสอบ
print(is_prime(17))  # True
print(is_prime(4))   # False
print(is_prime(2))   # True

หมายเหตุ: โค้ดต้นฉบับใช้ range(2, num//2) ขาด +1 ทำให้ตรวจสอบไม่ครบ (เช่น 4 จะไม่เจอตัวหาร 2) โค้ดข้างต้นแก้ไขแล้ว