แบ่งปันกันหน่อย สำหรับเพื่อนๆ ที่เรียน programming
เนื่องจากผมและเพื่อนๆ รหัส 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+2 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
จาก http://www.darun29.com/b2/(prime-number)/
ไม่มีความคิดเห็น:
แสดงความคิดเห็น