최대공약수, 소인수분해로 끝내버리기

 

최대공약수, 최소공배수.
공식으로 외우지 마!
사실, 너무너무 쉬운, 겹치는거 세는 문제야.

---

1. 일단 숫자 말고, 공부터 보자

두 친구 A랑 B가 있어.

A는
🔴 빨간공 3개
🔵 파란공 1개

B는
🔴 빨간공 2개
🔵 파란공 3개

자.
둘이 겹치게 가지고 있는 공은 뭐야?

빨간공은 최대 2개는 겹치지?
파란공은 최대 1개.

그래서

👉 🔴 2개
👉 🔵 1개

끝.

이게 바로 최대공약수야.

---

2. 이제 숫자로 바꿔보자

A = 2³ × 3¹
B = 2² × 3³

소인수분해란?
수를 소수들의 곱으로 쪼개는 거.

근데 곱셈을 머릿속에서 지워봐.

2는 빨간공
3은 파란공

이라고 생각하면

A는 2가 3개, 3이 1개
B는 2가 2개, 3이 3개

아까 공 문제랑
완전히 똑같아.

진짜로.

---

3. 최대공약수는 뭐라고?

겹치는 개수만 가져가는 거.

그래서

2는 min(3,2) → 2²
3은 min(1,3) → 3¹

따라서

GCD = 2² × 3¹ = 12

어렵다고 느껴졌다면
그건 곱셈 때문이야.

사실은 그냥
“두 숫자가 있다. 소인수분해를 했을 때, 겹치는 소인수는?”

 

이어질 내용은 뭐? 최소공배수!

https://cronix.tistory.com/121

최소공배수, 소인수분해로 끝내버리기

 

---