Python สอนเขียนฟังก์ชันตรวจสอบจำนวนเฉพาะ (Prime Number) ด้วย Python

Prime Number คืออะไร?

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

• 1

• ตัวมันเอง

ตัวอย่าง

• จำนวนเฉพาะ: 2, 3, 5, 7, 11, 13, 17

• ไม่ใช่จำนวนเฉพาะ: 0, 1, 4, 6, 8, 9, 10

---

โค้ด

def check_prime(n):
    if (type(n) != int):
        return False

    if (n < 2):
        return False

    if (n == 2):
        return True

    if (n % 2 == 0):
        return False

    for i in range(3, (n//2) + 1):
        if (n % i == 0):
            return False

    return True

---

อธิบายทีละขั้นตอน

1. ตรวจสอบชนิดข้อมูล

if (type(n) != int):
    return False

ฟังก์ชันนี้รับเฉพาะ จำนวนเต็ม (Integer)

หากส่งข้อมูลประเภทอื่นเข้ามา เช่น

check_prime(3.14)
check_prime("10")
check_prime([5])

จะคืนค่า

False

ทันที

---

2. ตรวจสอบค่าที่น้อยกว่า 2

if (n < 2):
    return False

ตามนิยาม

จำนวนเฉพาะต้อง มากกว่าหรือเท่ากับ 2

ดังนั้น

-10
-5
0
1

ไม่ใช่จำนวนเฉพาะทั้งหมด

---

3. กรณีพิเศษของเลข 2

if (n == 2):
    return True

เลข 2 เป็นจำนวนเฉพาะเพียงตัวเดียวที่เป็นเลขคู่

จึงตรวจสอบแยกไว้ก่อน

---

4. ตัดเลขคู่ทั้งหมดทิ้ง

if (n % 2 == 0):
    return False

เครื่องหมาย % คือ Modulus (หารเอาเศษ)

เช่น

4 % 2 = 0
6 % 2 = 0
20 % 2 = 0

ถ้าเศษเป็น 0 แสดงว่าหาร 2 ลงตัว

จึงไม่ใช่จำนวนเฉพาะ (ยกเว้นเลข 2 ที่ตรวจไปแล้ว)

ขั้นตอนนี้ช่วยลดการคำนวณได้มาก

---

5. ตรวจสอบตัวหาร

for i in range(3, (n//2)+1):

เริ่มตรวจจาก

3
4
5
...
จนถึง n//2

ตัวอย่าง

n = 17

ตรวจ

3
4
5
6
7
8

หากมีตัวใดหารลงตัว

if (n % i == 0):
    return False

แสดงว่าไม่ใช่จำนวนเฉพาะ

ตัวอย่าง

15

15 % 3 = 0

จึงคืน False

---

6. หากตรวจครบแล้วยังไม่พบตัวหาร

return True

หมายความว่า

ไม่มีจำนวนใดหารลงตัวเลย

จึงเป็นจำนวนเฉพาะ

เช่น

3
5
7
11
13
17
19
23
29

---

ทดสอบฟังก์ชัน

for i in range(-5,30):
    print(f"check_prime({i}) = {check_prime(i)}")

คำสั่งนี้จะทดสอบตัวเลขตั้งแต่

-5 ถึง 29

และแสดงผลลัพธ์ เช่น

check_prime(-5) = False
check_prime(-4) = False
check_prime(-3) = False
...
check_prime(2) = True
check_prime(3) = True
check_prime(4) = False
check_prime(5) = True
...
check_prime(29) = True

---

วิเคราะห์เวลาในการทำงาน (Time Complexity)

ลูปทำงาน

range(3, n//2 + 1)

ในกรณีแย่ที่สุด จะตรวจประมาณ

n/2 ครั้ง

ดังนั้น

Time Complexity

O(n)

เนื่องจากจำนวนรอบเพิ่มขึ้นตามค่าของ n

---

สามารถปรับปรุงให้เร็วขึ้นได้

หลักการทางคณิตศาสตร์บอกว่า

หากจำนวนหนึ่งมีตัวหาร นอกจาก 1 และตัวมันเอง จะต้องมีตัวหารอย่างน้อยหนึ่งตัวที่ไม่เกิน √n

ดังนั้น

แทนที่จะตรวจถึง

n/2

สามารถตรวจเพียง

√n

ก็เพียงพอ

ตัวอย่าง

n = 100

เดิมตรวจถึง 50

แต่จริง ๆ ตรวจถึง 10 ก็พอ

ทำให้ลดจำนวนรอบลงอย่างมาก

และ Time Complexity ดีขึ้นเป็น

O(√n)

จึงเป็นวิธีที่นิยมใช้ในงานจริง

---

สรุป

โค้ดนี้สอนหลักการตรวจสอบจำนวนเฉพาะอย่างเป็นลำดับ ได้แก่

• ตรวจสอบชนิดข้อมูลก่อน

• ตัดค่าที่น้อยกว่า 2 ออก

• แยกกรณีพิเศษของเลข 2

• ตัดเลขคู่ทั้งหมดออก

• ตรวจสอบตัวหารตั้งแต่ 3 ถึง n/2

• หากไม่พบตัวหาร แสดงว่าเป็นจำนวนเฉพาะ

แม้โค้ดนี้จะทำงานได้ถูกต้อง แต่ยังไม่ใช่วิธีที่มีประสิทธิภาพที่สุด เพราะยังตรวจสอบตัวหารมากเกินความจำเป็น การปรับให้ตรวจถึงเพียง √n จะช่วยให้โปรแกรมทำงานได้เร็วขึ้นอย่างเห็นได้ชัด โดยเฉพาะเมื่อใช้กับจำนวนที่มีค่ามาก