ตรวจจำนวนเฉพาะใน Python
ในบทเรียนนี้ คุณจะตรวจว่าตัวเลขเป็นจำนวนเฉพาะหรือไม่ โดยทดสอบตัวหารถึงแค่รากที่สองของมัน
บทนำ
ปัญหาที่ต้องแก้
จำนวนเฉพาะอยู่เบื้องหลังการเข้ารหัสบนอินเทอร์เน็ต 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 กับตัวมันเอง
ประเด็นสำคัญ
is_prime = number > 1ได้ค่าเริ่มต้นเป็น False สำหรับ 0, 1 และจำนวนติดลบ ซึ่งไม่มีทางเป็นจำนวนเฉพาะwhile divisor * divisor <= number and is_prime:หยุดที่รากที่สองหรือทันทีที่เจอตัวหารnumber % divisor == 0หมายความว่าdivisorหารตัวเลขนั้นลงตัวพอดี- สำหรับ 29 ลูปลองแค่ 2, 3, 4 และ 5 ก่อนจะบอกได้ว่าเป็นจำนวนเฉพาะ
ใช้เมื่อไร?
- โจทย์ตัวเลขและแบบฝึกหัด เช่น แสดงรายการจำนวนเฉพาะหรือแยกตัวประกอบเฉพาะ
- เรียนรู้ว่าทำไมการหยุดลูปก่อนกำหนด และการตรวจแค่ถึงขีดจำกัด ทำให้ลูปเร็วขึ้น
- ตรวจสอบอินพุตในเครื่องมือคณิตศาสตร์
เมื่อไรยังไม่จำเป็น
- แสดงจำนวนเฉพาะทั้งหมดจนถึงขีดจำกัดสูง ๆ: ตะแกรงของเอราทอสเทนีสเร็วกว่าการตรวจทีละตัวมาก
- การเข้ารหัสที่ใช้ตัวเลขยาวหลายร้อยหลัก: ระบบจริงใช้การทดสอบเชิงความน่าจะเป็น
โค้ดตัวอย่าง
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}")
ผลลัพธ์จากการรัน
29 is prime: True
อธิบายโค้ด
ลูปต้องทดสอบตัวหารเพียงตราบใดที่ divisor * divisor <= number เพราะถ้า n มีตัวหารที่มากกว่ารากที่สอง ตัวหารนั้นจะจับคู่กับตัวหารที่เล็กกว่าซึ่งลูปทดสอบไปแล้ว ความซับซ้อนจึงลดลงเหลือ O(√n) และผลลัพธ์แสดงว่า 29 เป็นจำนวนเฉพาะ
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง 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:
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- ตรวจสอบจำนวนเฉพาะ ตัดสินว่าตัวเลขเป็นจำนวนเฉพาะหรือไม่ ง่าย
- ตัวประกอบเฉพาะที่มากที่สุด หาตัวเลขเฉพาะที่มากที่สุดซึ่งหารจำนวนเต็มบวกหนึ่งจำนวนได้ลงตัว ปานกลาง
- List Primes With a Sieve Find primes up to a limit by marking composite multiples. ปานกลาง