การทดสอบจำนวนเฉพาะถึง sqrt(n)

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

คุณอาจลองหาร n ด้วยทุกจำนวนตั้งแต่ 2 จนถึง n ลบ 1 วิธีนี้ถูกต้อง แต่ ช้าอย่างมากเมื่อ n มีขนาดใหญ่

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

ตัวหารมาเป็นคู่ที่คูณกันได้ n หากทั้งคู่มากกว่ารากที่สอง ผลคูณของทั้งคู่จะมากกว่า n ซึ่งเป็นไปไม่ได้

วนค่า i ตั้งแต่ 2 ตราบใดที่ i คูณ i ยังน้อยกว่าหรือเท่ากับ n การใช้ i*i ช่วยหลีกเลี่ยงข้อผิดพลาดของเลขทศนิยมจาก รากที่สองเมื่อใช้กับจำนวนเต็มขนาดใหญ่

ตัวเลขที่น้อยกว่า 2 ไม่เป็นจำนวนเฉพาะ ดังนั้นให้ปฏิเสธตั้งแต่ต้น การตรวจป้องกันนี้ช่วยให้ลูปหลักสะอาดและถูกต้อง

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

ตรวจ 2 แยกต่างหาก แล้วทดสอบเฉพาะจำนวนคี่ การข้ามจำนวนคู่ช่วยลดงานลงประมาณครึ่งหนึ่งโดยไม่เพิ่มความซับซ้อน

การทดสอบนี้ใช้เวลา O(sqrt n) สำหรับจำนวนเดียวที่ไม่เกินหนึ่งพันล้าน จะมีการดำเนินการราคาถูกเพียงประมาณ 30,000 ครั้งเท่านั้น

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

การเปรียบเทียบด้วย i*i แทน math.sqrt ช่วยหลีกเลี่ยงข้อผิดพลาดจากการปัดเศษ ซึ่งอาจทำให้ยอมรับหรือปฏิเสธตัวเลขที่อยู่ตรงขอบเขตอย่างไม่ถูกต้อง

ยืนยันขอบเขตที่ทำให้การทดสอบนี้รวดเร็ว

ตอนนี้คุณสามารถทดสอบว่าตัวเลขหนึ่งจำนวนเป็นจำนวนเฉพาะหรือไม่ด้วยเวลา O(sqrt n) ตรวจป้องกันค่าขนาดเล็ก ข้ามจำนวนคู่ และใช้ i*i เพื่อรักษาความแม่นยำได้แล้ว ✅