หารร่วมมาก (Great Common Divisor)

ช่วงนี้ไม่รู้นึกอะไรชอบไปเล่น http://programming.in.th/ แล้วก็เจอข้อหาการหารร่วมมาก ตอนแรกก็นั่งนึกอยู่นานว่าจะทำยังไงดีเลยลองหาใน wiki ดูปรากฎว่ามันมีอัลกอริทึมชื่อว่า "Euclid" หาได้โดย


gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)


ง่ายขิงๆ :)