วิธีของยุคลิด (Euclidean Algorithm)
การตรวจสอบจำนวนนับนั้นว่าเป็นจำนวนเฉพาะหรือไม่ การหา ห.ร.ม.(ตัวหารร่วมมาก) ของจำนวนนับสองจำนวนที่มีค่ามากเพื่อให้หาได้สะดวกและรวดเร็ว เราไปดูรายละเอียด
จำนวนนับที่มากกว่า 1 และมีตัวประกอบเพียงสองตัว คือ 1 และตัวของมันเอง เรียกว่า จำนวนเฉพาะ (Prime number) เช่น 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 , … เติมจำนวนเฉพาะ 1,000 จำนวนแรก
นำแนวคิดเดียวกันมาตรวจสอบได้ ดังนี้
ตัวอย่างที่ 1 จงตรวจสอบว่า 83 เป็นจำนวนเฉพาะหรือไม่
วิธีทำ ขั้นที่ 1 จำนวนเฉพาะทุกจำนวนที่คูณตัวเอง แล้วผลคูณไม่เกิน 83 คือ 2, 3, 5, 7
………ขั้นที่ 2 นำ 2, 3, 5, 7 ไปหาร 83 ผลปรากฏว่า ไม่มีจำนวนเฉพาะจำนวนใดหาร 83 ลงตัว
………ดังนั้น 83 เป็นจำนวนเฉพาะ
ตัวอย่างที่ 2 จงตรวจสอบว่า 161 เป็นจำนวนเฉพาะหรือไม่
วิธีทำ ขั้นที่ 1 จำนวนเฉพาะทุกจำนวนที่คูณตัวเอง แล้วผลคูณไม่เกิน 161 คือ 2, 3, 5, 7, 11
………ขั้นที่ 2 นำ 2, 3, 5, 7, 11 ไปหาร 161 ผลปรากฏว่า 7 หาร 161 ลงตัว (161 = 7×23)
………ดังนั้น 161 ไม่เป็นจำนวนเฉพาะ
…….การหา ห.ร.ม. (ตัวหารร่วมมาก) ของจำนวนนับสองจำนวน ที่มีค่ามาก มีหลายวิธี แต่วิธีที่รวดเร็วคือ ขั้นตอนวิธีของยุคลิด (Euclidean algorithm)
