ตัวคูณร่วมน้อย (Least Common Multiple ) และ ตัวหารร่วมมาก (Greatest Common Divisor)

ตัวคูณร่วมน้อย หรือ Least Common Multiple (ครน.,  LCM) ของจำนวนเต็มตั้งแต่สองจำนวนขึ้นไป  คือจำนวนเต็มที่มีค่าน้อยที่สุดที่จำนวนเต็มทุกตัวที่กำหนดไว้หารได้ลงตัว เช่น  2 และ 3 มี ครน. คือ 6  เพราะ 6 คือจำนวนเต็มที่มีค่าน้อยที่สุดที่ทั้ง 2 และ 3 หารได้ลงตัว อาจเขียนแทนด้วย
LCM(2,3) = 6

การหาค่า LCM
1. นำตัวเลขที่ต้องการมาหาตัวคูณของตัวเอง
2. หาตัวคูณตัวแรกที่ซ้ำกัน
เช่น

ตัวเลข	ตัวคูณ
3	3,6,9,12,15,18
5	5,10,15,20,25,30

ตัวคูณตัวแรกที่ซ้ำกันคือ 15 , LCM(3,5) = 15

ตัวเลข	ตัวคูณ
2	2,4,6,8,10,12
4	4,8,12,16
6	6,12,18

ตัวคูณตัวแรกที่ซ้ำกันคือ 12, LCM(2,4,6) = 12

ตัวหารร่วมมาก หรือ Greatest Common Divisor (หรม., GCD) ของจำนวนเต็มตั้งแต่สองจำนวนขึ้นไป  คือจำนวนเต็มที่มีค่ามากที่สุดที่หารจำนวนเต็มทุกตัวที่กำหนดไว้หารได้ลงตัว เช่น  12 และ 8 มี หรม. คือ 4  เพราะ 4 คือจำนวนเต็มที่มีค่ามากที่สุดที่หารทั้ง 12 และ 8 ได้ลงตัว อาจเขียนแทนด้วย GCD(12,8) = 4

การหาค่า GCD
1. นำตัวเลขที่ต้องการมาหาตัวประกอบ
2. หาตัวประกอบร่วมที่มีค่ามากที่สุด

ตัวเลข	ตัวประกอบ
12	1, 2, 3, 4, 6, 12
30	1, 2, 3 , 5, 6 ,10, 15, 30

ตัวประกอบร่วมที่มีค่ามากที่สุดคือ 6, GCD(12,30) = 6

การหาค่า GCD ด้วย prime factor
prime factor คือตัวประกอบที่เป็น prime number (จำนวนที่มี 1 และตัวมันเองที่หารลงตัว) เช่น 2, 3, 5, 7,11,13, 17,...

ตัวเลข	ตัวประกอบ prime factors
24	2 x 2 x 2 x 3
108	2 x 2 x 3 x 3 x 3

จะเห็นว่ามี 2 เป็น factor ร่วมกัน 2 ตัว และ 3 เป็น factor ซ้ำกัน 1 ตัว นำ factor ที่ซ้ำกันทั้งหมดมาคูณกัน 2 x 2 x 3 = 12

---

def gcd(a,b):
 """This function implements the Euclidian algorithm
 to find G.C.D. of two numbers
 https://en.wikipedia.org/wiki/Euclidean_algorithm
 """
 while b:
  a,b = b,a%b
 return a

# define lcm function
def lcm(x, y):
 """This function takes two
 integers and returns the L.C.M."""

 lcm = (x*y)//gcd(x,y)
 return lcm

print(gcd(3,4))
print(lcm(3,5))

---