제로베이스 데이터사이언스 스쿨 - Part 03. 기초 수학-16

 Chapter 02. 기초수학 문제풀이

 

소인수분해와 최대공약수 (Python 기초 실습)

 

주요 개념

이번 강의에서는 소인수(prime factor), 소인수분해(prime factorization),
그리고 최대공약수(GCD, Greatest Common Divisor) 개념을 중심으로 실습을 진행했다.

---

1. 소인수와 소인수분해

소인수분해란 하나의 수를 소수들의 곱으로 표현하는 것이다.
예를 들어 20을 소인수분해하면

20 = 2 × 2 × 5 → (2² × 5¹)

즉, 소인수는 [2, 5], 각 소인수의 지수는 [2, 1]이 된다.

---

소인수분해 코드 예시

import random

rNum = random.randint(100, 1000)
print(f'rNum: {rNum}')

soinsuList = []
n = 2

while n <= rNum:
    if rNum % n == 0:
        print(f'소인수: {n}')
        soinsuList.append(n)
        rNum /= n
    else:
        n += 1

print(f'soinsuList: {soinsuList}')

tempNum = 0
for s in soinsuList:
    if tempNum != s:
        print(f'{s}의 개수: {soinsuList.count(s)}')
        tempNum = s

 

실행 결과 예시

 

rNum: 899
소인수: 103
소인수: 103
소인수: 103
soinsuList: [103, 103, 103]
103의 개수: 3

 

이처럼 반복문과 리스트 카운트 기능을 활용하면
각 소인수의 등장 횟수(지수)를 출력할 수 있다.

---

2. 최대공약수 (GCD)

두 수의 공약수(common divisor) 중 가장 큰 수를 의미한다.
예를 들어

12의 약수 = [1, 2, 3, 4, 6, 12]
20의 약수 = [1, 2, 4, 5, 10, 20]
→ 공약수 = [1, 2, 4] → 최대공약수 = 4

---

최대공약수 코드 예시

import random

rNum1 = random.randint(100, 1000)
rNum2 = random.randint(100, 1000)
print(f'rNum1: {rNum1}')
print(f'rNum2: {rNum2}')

maxNum = 0

for n in range(1, (min(rNum1, rNum2) + 1)):
    if rNum1 % n == 0 and rNum2 % n == 0:
        print(f'공약수: {n}')
        maxNum = n

print(f'최대공약수: {maxNum}')

if maxNum == 1:
    print(f'{rNum1}과 {rNum2}는 서로소입니다.')

 

실행 결과 예시

 

rNum1: 348
rNum2: 609
공약수: 1
공약수: 3
공약수: 29
공약수: 87
최대공약수: 87

 

* 이 글은 제로베이스 데이터사이언스 파트타임 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.

---

 

💡 생각 정리

이번 실습은 소수와 약수 개념의 응용편이었다.
이전 강의에서 배운 “약수와 소수” 개념이 실제로 소인수분해와 최대공약수 계산에 어떻게 확장되는지 직접 구현해볼 수 있었다.

특히 while문을 이용해 나눗셈을 반복하면서 소인수를 추출하는 로직이 흥미로웠고, list.count()로 각 소인수의 지수를 계산하는 방식이 직관적이었다.

또한 두 수의 최대공약수를 직접 찾아보며 “공약수 리스트 중 가장 큰 값이 GCD”라는 개념을 명확히 체득할 수 있었다.

---

🚀 적용점

 

• 유클리드 호제법(Euclidean Algorithm) 으로 확장 가능
• 최소공배수(LCM) 계산 프로그램 구현의 기초
• 수학적 패턴 탐색 프로그램 제작 시 활용 가능
• 소인수분해 기반 암호 알고리즘(예: RSA) 개념의 이해에 도움