들어가며

이번 포스팅에서는 소인수 분해에 대해 다뤄볼까 합니다. 😉

소인수 분해는 중학생 때 배울 정도로 쉬운 개념이지만, 알고리즘으르 짜는 것(코딩으로 구현하는 것)은 다른 영역이기 때문에 포스팅을 통해 남겨두고자 합니다.

1. 소인수 분해

소인수 분해

소인수 분해 (Prime Factorization)란

소인수 분해란 어떠한 숫자를 1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것을 말합니다.

소인수

인수 : 어떤수를 곱하기로 표현했을 때 곱해지는 각각의 수들
소인수 : 인수 중에서 소수인 것

• 6의 인수 : 1, 2, 3, 6
• 6의 소인수 : 2, 3

소수

여기서 소수는 1과 자기 자신 만의 곱으로만 이루어진 수입니다. 다르게 말하면 1과 자기 자신 외에 약수를 갖지 않습니다.

예를 들어, 2는 1 * 2의 곱으로 표현할 수 있습니다

• 5 = 1 * 5
• 7 = 1 * 7
• 17 = 1 * 17

숫자 12의 약수는 {1, 2, 3, 4, 6, 12}으로 정리되며, 2 * 6, 3 * 4 등으로 표현될 수 있어 소수가 아닙니다

소인수 분해하는 방법

소인수분해를 하는 가장 간단한 방법은 다음과 같습니다.

1. 해당 합성수를 소인수로 몫이 소수가 될 때까지 나눗셈을 계속합니다.
2. 사용된 모든 소인수와 마지막 몫을 지수의 형태로 곱합니다.

예제) 72를 소인수분해하시오.

코드

소인수는 2부터 시작하여 2로 나누지 못할 경우 2에서 +1를 해주면서 나누어지는지 체크하면 됩니다.

왜 2부터 시작하느냐? 하면 아래 코드를 통해 알 수 있습니다.

def factorization(n):
	result = []
    i = 2
    for i <= n:
    	if n % i == 0:
        	n //= i
            # 인수 목록만 구할 경우
            # if i in result:
            result.append(i)
        else:
        	i += 1
	return result

2. 실전 문제

https://school.programmers.co.kr/learn/courses/30/lessons/120852

References

• 소인수분해 하는 법, 인수와 소인수의 뜻
• 소수와 소인수분해