Prime Number Algorithm

จำนวนเฉพาะ (Prime Number) คือจำนวนที่หาร 1 และตัวมันเองลงตัวเท่านั้น ...

เจอมาทุกปีครับ เราท่องกันมาแบบนี้ แต่เวลาเขียนโปรแกรมมันเป็นแบบนั้นซะที่ไหนล่ะ 

ผมเจอโค้ดแบบนี้ล่ะปวดหัว แต่ก็เจอมาทุกปี

โดยในการตรวจสอบว่า "เลขจำนวนเต็มบวกใดๆ" เป็นจำนวนเฉพาะหรือไม่ 

มีวิธีมากมาย วันนี้ผมจะเสนอ 3 วิธี และวิธีที่ง่ายที่สุด ก็คือ

นำเลข 2 จนถึง N-1 (โดยที่ N คือจำนวนเต็มใดๆ ที่ต้องการตรวจสอบ) ว่า N หารลงตัวหรือไม่ ถ้าในระหว่างนี้มีการหารลงตัวเกิดขึ้น นั่นแปลว่าเลขที่รับเข้ามาไม่เป็นจำนวนเฉพาะ แต่ถ้าหารไม่ลงตัวเลย (หลุด Loop มาได้) ก็แปลว่าเลขนั้นเป็นจำนวนเฉพาะ

โดยจะเขียนโปรแกรมในภาษา Ruby ได้ดังนี้ 

แต่วิธีนี้เป็นวิธีที่ช้ามาก ... ก็มีวิธีที่เร็วกว่านั้นคือแทนที่จะหารด้วย 2 ถึง N-1 ให้เราหารถึงแค่ √N แทน

เพราะว่าในบรรดาคู่ของตัวเลข (a, b) ที่คูณกันแล้วได้ N ทั้งหมดนั้น จะไม่มีค่า a ที่มากกว่าค่าของรากที่ 2 ของ N เช่น คู่ของตัวที่คูณกันได้ 100 มี (1, 100), (2, 50), (4, 25), (5, 20), (10, 10) ดังนั้นจึงไม่มีความจำเป็นที่ต้องทดสอบมากกว่า 10 เพราะตัวถัดไปที่จะเจอคือ 20 ซึ่งคู่กับ 5 อยู่ดี

ส่วนวิธีที่ 3 ที่จะบอกก็คือ Sieve of Eratosthenes

โดยวิธีการก็เป็นตัดตัวเลขที่ไม่ใช่ออกไป โดยการตัดตัวที่ Prime Number ใดๆ 

หารลงตัวออก ซึ่งจะเป็นไปตามภาพนี้ 

เท่านี้แหละครับ ลองไปทำความเข้าใจดูนะ ... ขอทิ้งท้ายด้วย Algorithm ที่ 2 (ซึ่งผมใช้บ่อย)

ในรูปแบบของภาษา C++ (ไม่มีอะไรต่างกับ C เพียงแต่ผมต้องการใช้ Boolean) ล่ะกันนะครับ