แบบฝึกหัด Python สำหรับผู้เริ่มต้น

ตรวจจำนวนเฉพาะใน Python

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

  • ระดับเริ่มต้น
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

จำนวนเฉพาะอยู่เบื้องหลังการเข้ารหัสบนอินเทอร์เน็ต hash table และโจทย์ปริศนาอีกมาก ถ้าตรวจว่าเป็นจำนวนเฉพาะไหมโดยลองหารด้วยทุกตัวจนถึงตัวมันเอง ก็ใช้ได้กับ 29 แต่ช้ามากกับตัวเลขใหญ่ แค่เข้าใจหลักง่าย ๆ ข้อเดียวก็ตรวจได้เร็วขึ้นมาก

ลองนึกภาพแบบนี้

การหาตัวหารเหมือนการลองปูกระเบื้องให้เป็นสี่เหลี่ยมผืนผ้าเต็มแผ่น กระเบื้อง 36 แผ่นปูได้เป็น 1×36, 2×18, 3×12, 4×9 และ 6×6 พอเลยสี่เหลี่ยมจัตุรัส (6×6) ไปแล้ว ก็จะเจอแต่สี่เหลี่ยมเดิมที่หมุนกลับด้าน จึงไม่มีอะไรใหม่ให้หาหลังรากที่สอง ส่วนกระเบื้อง 29 แผ่นปูได้แบบเดียวคือ 1×29 ดังนั้น 29 เป็นจำนวนเฉพาะ

จากการปูกระเบื้องสู่โค้ด
number > 1🚪 เฉพาะเลขที่มากกว่า 1 เท่านั้นที่เป็นจำนวนเฉพาะได้
divisor * divisor <= number🪞 หยุดที่สี่เหลี่ยมจัตุรัส: หลังจากนั้นเป็นแบบซ้ำ
number % divisor == 0🔍 ปูได้เต็มสี่เหลี่ยม: ไม่ใช่จำนวนเฉพาะ
divisor += 1➡️ ลองความกว้างถัดไป
ถ้าไม่เจอตัวหารจนถึงรากที่สอง ตัวเลขนั้นเป็นจำนวนเฉพาะ
สรุปในประโยคเดียว

จำนวนเฉพาะคือจำนวนเต็มที่มากกว่า 1 ซึ่งมีตัวหารบวกเพียง 1 กับตัวมันเอง

ประเด็นสำคัญ

  1. is_prime = number > 1 ได้ค่าเริ่มต้นเป็น False สำหรับ 0, 1 และจำนวนติดลบ ซึ่งไม่มีทางเป็นจำนวนเฉพาะ
  2. while divisor * divisor <= number and is_prime: หยุดที่รากที่สองหรือทันทีที่เจอตัวหาร
  3. number % divisor == 0 หมายความว่า divisor หารตัวเลขนั้นลงตัวพอดี
  4. สำหรับ 29 ลูปลองแค่ 2, 3, 4 และ 5 ก่อนจะบอกได้ว่าเป็นจำนวนเฉพาะ

ใช้เมื่อไร?

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

เมื่อไรยังไม่จำเป็น

  • แสดงจำนวนเฉพาะทั้งหมดจนถึงขีดจำกัดสูง ๆ: ตะแกรงของเอราทอสเทนีสเร็วกว่าการตรวจทีละตัวมาก
  • การเข้ารหัสที่ใช้ตัวเลขยาวหลายร้อยหลัก: ระบบจริงใช้การทดสอบเชิงความน่าจะเป็น

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

รันโค้ด →
main.py
number = 29
is_prime = number > 1

divisor = 2
while divisor * divisor <= number and is_prime:
    if number % divisor == 0:
        is_prime = False
    divisor += 1

print(f"{number} is prime: {is_prime}")
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

29 is prime: True

อธิบายโค้ด

ลูปต้องทดสอบตัวหารเพียงตราบใดที่ divisor * divisor <= number เพราะถ้า n มีตัวหารที่มากกว่ารากที่สอง ตัวหารนั้นจะจับคู่กับตัวหารที่เล็กกว่าซึ่งลูปทดสอบไปแล้ว ความซับซ้อนจึงลดลงเหลือ O(√n) และผลลัพธ์แสดงว่า 29 เป็นจำนวนเฉพาะ

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. เปลี่ยนข้อมูลอินพุตแล้วทายผลลัพธ์ก่อนรัน
  2. เพิ่มการตรวจสอบข้อมูลว่างหรือข้อมูลที่ไม่ถูกต้อง
  3. แยกขั้นตอนการประมวลผลเป็นฟังก์ชันและทดสอบกับข้อมูลหลายชุด
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ถือว่า 1 เป็นจำนวนเฉพาะ

1 มีตัวหารเพียงตัวเดียว จึงไม่ใช่จำนวนเฉพาะ ให้ตรวจ number > 1 ก่อน

ปัญหา
is_prime = True  # 1 would be reported as prime
วิธีแก้
is_prime = number > 1

วนลูปไปจนถึงตัวเลขนั้น

คำตอบถูก แต่ลองตัวหารมากเกินความจำเป็นไปมาก

ปัญหา
for divisor in range(2, number):
วิธีแก้
while divisor * divisor <= number:

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: กลับด้านสตริงใน Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด