소인수분해 — 수를 소수의 곱으로 분해하기

360이라는 수를 보면 어떤 생각이 드나요? 사실 $360 = 2^{3} \times 3^{2} \times 5$ 입니다. 이처럼 자연수를 소수들의 곱으로 표현하는 것을 소인수분해라고 합니다. 한 번 분해하면 그 수의 모든 비밀이 드러납니다.

1. 소수(素數)란?

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.

소수인지 판별하려면 $n$ 이하의 소수로 나누어보면 됩니다.

60을 소인수분해

        60
       /  \
      2   30
         /  \
        2   15
           /  \
          3    5

60 = 2 × 2 × 3 × 5 = 2² × 3 × 5

2 | 360
2 | 180
2 |  90
3 |  45
3 |  15
5 |   5
    1

360 = 2³ × 3² × 5

같은 소수가 여러 번 나올 때는 지수로 나타냅니다.

$2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^{3} \times 3^{2} \times 5$

$n = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times \dots$ 이면:

$약수의 개수 = (a_{1} + 1) (a_{2} + 1) \dots$

72 = 2³ × 3²
약수의 개수 = (3+1)(2+1) = 4 × 3 = 12개

공통 소인수를 낮은 지수로 곱합니다.

GCD(72, 120)

72  = 2³ × 3²
120 = 2³ × 3 × 5

공통 소인수: 2³, 3¹
GCD = 2³ × 3 = 8 × 3 = 24

모든 소인수를 높은 지수로 곱합니다.

LCM(72, 120)

72  = 2³ × 3²
120 = 2³ × 3 × 5

모든 소인수: 2³, 3², 5¹
LCM = 2³ × 3² × 5 = 8 × 9 × 5 = 360

$GCD (a, b) \times LCM (a, b) = a \times b$

GCD(72,120) × LCM(72,120) = 72 × 120
24 × 360 = 8,640  ✓