ถ้าให้
n เป็นเลขจำนวนเต็มที่มีค่ามากกว่า 1
n = p1n1 p2n2...pknk
เมื่อ
p คือเลขจำนวนเฉพาะ
p1 < p2 < ... < pk
n1, n2, n3, ...nk เป็นเลขจำนวนเต็ม
> 0
k >= 1
ตัวอย่างเช่น
28 = 22 x 50 x 71
200 = 23 x 52 x 70
-------------------------------------------------------------------------------
| ห.ร.ม. คืออะไร |
ลองดูจากตัวอย่างง่าย
ๆ ตัวอย่างหนึ่ง
|
|
| จากตัวเลข 8 = 23 x 30 |  |
| จากตัวเลข 12 = 22 x 30 |
| หลักการ ห.ร.ม. |
สมมุติว่าเรามีตัวเลขจำนวนเต็มบวกสองตัว a และ b เราจะหาตัวหารร่วมได้อย่างไร
หรืออาจกล่าวได้ว่า di น้อยกว่าค่าน้อยสุดระหว่าง ai,
bi
แต่ถ้าจะให้เป็นตัวหารร่วมที่มากที่สุด
(ห.ร.ม.) ค่า di จะต้องเท่ากับค่าน้อยที่สุดระหว่าง ai,
bi
di = min(ai, bi)
| อัลกอริทึมของยูคลิด สำหรับการหา ห.ร.ม. | ตัวอย่างโปรแกรมด้วยปาสคาลหา ห.ร.ม. ด้วยอัลกอริทึมของยูคลิด |