소인수 분해는 어떤 수 소인수의 곱으로 나타낼때, 약수를 찾을때 많이 씀.
소인수
소인수 = 소수 + 인수(=약수)
약수(=인수)중에서 소수인 숫자를 소인수라고 한다.
| 20의 약수(인수) → |
1 2 4 5 10 20
│ │
▽ ▽
소수 소수
└─┬─┘
▽
소인수 |
- 12의 인수: 1, 2, 3, 4, 6, 12 소인수: 2, 3
- 36의 인수: 1, 2, 3, 4, 9, 12, 18, 36 소인수: 2, 3
- 25의 인수: 1, 5, 20 소인수: 5
- 41의 인수: 1, 41 소인수: 41
소인수분해
1보다 큰 정수를 소인수의 곱으로 나타낸 것을 소인수분해라고 한다.
20의 소인수분해 →
|
2 × 10
│
▽
2 × 5
───────────
↓
2 × 2 × 5
↓
2^2 × 5 |
- 12의 인수: 1, 2, 3, 4, 6, 12 소인수: 2, 3
12의 소인수분해: 2^2 × 3
- 36의 인수: 1, 2, 3, 4, 9, 12, 18, 36 소인수: 2, 3
36의 소인수분해: 2^2 × 3^2
- 25의 인수: 1, 5, 20 소인수: 5
25의 소인수분해: 5^2
- 41의 인수: 1, 41 소인수: 41
41의 소인수분해: 41
소인수분해와 약수
소인수분해를 이용해서 약수를 정확하고 쉽게 구할 수 있다.
20의 소인수분해 →
|
2^2 × 5
|
20의 약수(인수) →
|
2^2 × 5
↓
× │ 5
───┼───────
2^2 │
↓
× │ 1 5
───┼───────
1 │ 1 5
2 │ 2 10
2^2 │ 4 20
↓
1 2 4 5 10 20 |
[실습]
다음의 수를 소인수분해를 통해서 약수를 구해보자.
- 14 → 소인수분해: 2 × 7
× │ 1 7
──┼────
1 │ 1 7
2 │ 2 14
약수(인수) : 1, 2, 7, 14
- 154 → 소인수분해: 2 × 77 ─▷ 2 × 7 × 11
× │ 1 11
───┼─────
1 │ 1 11
2 │ 2 22
7 │ 7 77
2 × 7 │ 14 154
약수(인수) : 1, 2, 7, 11, 14, 22, 77, 154
- 1547 → 소인수분해: 7 × 221 ─▷ 7 × 13 × 17
× │ 1 17
───┼─────
1 │ 1 17
7 │ 7 119
13 │ 13 221
7 × 13 │ 91 1547
약수(인수) : 1, 7, 13, 17, 91, 119, 221, 1547
- 2025 → 소인수분해: 5 × 405 ─▷ 5 × 5 × 81 ─▷ 5 × 5 × 3 × 27 ─▷ 5 × 5 × 3 × 3 × 9
─▷ 5 × 5 × 3 × 3 × 3 × 3 ─▷ 5^2 × 3^4
× │ 1 3 9 27 3^4
───┼──────────────────
1 │ 1 3 9 27 81
5 │ 5 15 45 135 405
5^2 │ 25 75 225 675 2025
약수(인수) : 1, 3, 5, 9, 15, 25, 27, 45, 75, 81, 135, 225, 405, 675, 2205
파이썬 이용
파이썬을 이용해서 사용자가 입력한 수를 소인수분해해보자.
inputNumber = int(input('1보다 큰 정수 입력: '))
n = 2
while n <= inputNumber:
if inputNumber % n == 0:
print('소인수: {}'.format(n))
inputNumber /= n
else:
n += 1
| -- 출력 -- |
1보다 큰 정수 입력: 12
소인수: 2
소인수: 2
소인수: 3 |
[실습]
72에 x를 곱하면 y의 제곱이 된다고 할때, x에 해당하는 가장 작은 정수를 구하자.
| 72의 소인수분해 : |
2 × 36 → 2 × 2 × 18 → 2 × 2 × 2 × 9 → 2 × 2 × 2 × 3 × 3 → 2^3 × 3^2
|
72에 x를 곱하면 y의 제곱이 된다.
|
2^3 × 3^2 × ? = ?^2
제곱이 홀수이면, y의제곱으로 묶을수 없으므로, 제곱을 짝수로 만들어 준다.
↓
2^3 × 3^2 × 2 = ?^2
↓
2^4 × 3^2 = ?^2
↓
2^4 × 3^2 = (2^2 × 3)^2
|
inputNumber = int(input('1보다 큰 정수 입력: '))
n = 2
searchNumbers = []
# 제곱이 홀수이면, y의제곱으로 묶을수 없으므로, 값을 추가해서 제곱을 짝수로 만들어줄 수 있다.
# 그러므로 제곱이 홀수로 떨어질 소수를 찾아야한다.
while n <= inputNumber:
if inputNumber % n == 0:
print('소인수: {}'.format(n))
if searchNumbers.count(n) == 0: # 값이 없으면 (홀수) 리스트에 추가
searchNumbers.append(n)
elif searchNumbers.count(n) == 1: #값이 있으면 (짝수) 리스트에서 삭제
searchNumbers.remove(n)
inputNumber /= n #몫으로 나눈 나머지 저장
else:
n += 1
print('searchNumbers: {}'.format(searchNumbers))