เนื่องจากผมและเพื่อนๆ รหัส 52 มีโจทย์ฝึกเรื่องจำนวนเฉพาะ
เลยเอามาเขียนสักหน่อยเป็นการคลายเครียดหลังสอบเก็บคะแนน math2 T-T
จำนวนเฉพาะ (Prime Numbers)
คือจำนวนเต็มบวกที่ไม่มีเลขใดหารมันลงตัวนอกจาก 1 และตัวมันเอง และ 1 ไม่ใช่จำนวนเฉพาะ
วิธีการหาจำนวนเฉพาะ
แบบง่ายๆ
function is_prime(n)
for i=2 to i<n i=i+1
if n mod i = 0
return 0
return 1
วิธีการที่เร็วขึ้นมาอีก
function is_prime(n)
for i=2 to i<=sqrt(n) i=i+1
if n mod i = 0
return 0
return 1
วิธีนี้แทนที่เราจะเอาตัวเลขตั้งแต่ 2 ถึง n-1 มาลองหาร เราก็เอาแค่ 2 ถึง sqrt(n)
เหตุผลนั้น จำไม่ได้ -_- แต่สามารถอธิบายได้ด้วยคณิตศาสตร์
ปรับปรุงอัลกอฯ นิดหน่อย
function is_prime(n)
lim = sqrt(n)
for i=2 to i<=lim i=i+1
if n mod i = 0
return 0
return 1
เราหา sqrt(n) เก็บไว้ในตัวแปร จะทำให้เราไม่ต้องหา sqrt(n) ทุกรอบของ for
เปลี่ยนรูปของเงื่อนไข
function is_prime(n)
for i=2 to i*i<=n i=i+1
if n mod i = 0
return 0
return 1
วิธีนี้จะเร็วกว่าการวิธีการก่อนหน้านี้นิดนึง
ตรวจสอบจำนวนคู่
function is_prime(n)
if n = 2
return 1
if n mod 2 = 0
return 0
for i=3 to i<=sqrt(n) i=i+1
if n mod i = 0
return 0
return 1
เพราะเรารู้อยู่แล้วว่าจำนวนคู่ทุกตัวยกเว้นสองนั้นไม่ใช่จำนวนเฉพาะ
ง่ายๆ แค่นี้ ทำให้การหาจำนวนเฉพาะนั้นเร็วขึ้น
ยังเร็วไม่พอ?
มีความจริงอยู่ข้อหนึ่ง n จะเป็นจำนวนเฉพาะถ้าไม่มีจำนวนเฉพาะใดที่ต่ำกว่า sqrt(n) หาร n ลงตัว
ทำยังไงละ
*สมมุติว่าค่า n สูงสุดที่เราต้องการทราบว่าเป็นจำนวนเฉพาะหรือไม่คือ 2^31-1 (2,147,483,647) = ค่าสูงสุดของ
int 32bit
*สร้าง array ของจำนวนเฉพาะที่น้อยกว่า sqrt ของค่าสูงสุด (ประมาณ 46340.95) จะได้จำนวนเฉพาะทั้งหมด 479 ตัว
*จากนั้นนำจำนวนเฉพาะที่น้อยกว่าหรือเท่ากับค่า sqrt ของจำนวนที่ต้องทราบไปหาร ถ้าหารลงตัวแสดงว่าไม่ใช่จำนวนเฉพาะ
ไม่เข้าใจ?
สมมุติว่าค่าสูงสุดที่เราต้องการทราบคือ 100
function is_prime(n)
pre_prime = [2,3,5,7] # sqrt(100) = 10 เราจึงหาจำนวนเฉพาะที่น้อยกว่า 10
lim = sqrt(n)
i = 0
while i<4 and pre_prime<=lim
if n mod pre_prime = 0
return 0
i = i+1
return 1
จะเห็นว่าวิธีการนี้เร็วมาก แต่แลกด้วยกับการใช้หน่วยความจำที่มากขึ้น
อ้างอิงจากหนังสือ Art Of Programming Contest เขียนโดย Ahmed Shamsul Arefin
