이 포스트에서는 파이썬으로 소인수분해 알고리즘을 구현한 예를 소개합니다.
다음 코드를 봅시다.
n = input("2 이상의 자연수를 입력하세요: ")
try:
n = int(n)
except ValueError:
n = 0
if n >= 2: # Right
print("소인수분해할 수는 %d입니다." % n)
factorized_array = [] # Init
m = n
div, deg = 2, 0
while m > 1 or deg > 0: # Factorization
if m % div == 0: m //= div; deg += 1
else:
if deg >= 1: factorized_array.append( (div, deg) )
div += 1; deg = 0;
print("\n★ 소인수분해 결과 ★") # Print
if factorized_array[0][0] == n:
print("%d은(는) 소수입니다." % n)
else:
print("%d은(는) 합성수입니다." % n)
print("----")
for val in factorized_array: print(val)
print("----")
else: # Wrong
print("입력이 잘못되었습니다.")
먼저 1번 줄에서 자연수를 입력받습니다. 2번부터 5번까지는 예외처리 블록으로, 문자열 형태로 입력된 입력값을 정수형으로 바꾸되, 만약 바꿀 수 없는 예외처리가 발생하면 0으로 처리하는 것입니다.
7번 줄에서 소인수분해를 시작합니다. 만약 입력받은 자연수가 2 이상이면 진행하고 그렇지 않으면 27번 줄로 넘어가 입력이 잘못되었다는 메시지를 출력하고 종료합니다. 9번 줄에서 소인수분해 결과를 저장할 배열을 선언하고, 10번 줄에서 소인수분해에 사용할 값(이하 m)을 선언하고 입력값과 같은 값으로 초기화, 11번 줄에서 제수와 차수를 저장할 변수를 선언합니다.
12번 줄에서 반복이 시작되는데, 반복 조건은 m이 1보다 크거나 차수가 1 이상일 때입니다. 이렇게 설정하는 이유는 마지막 소인수를 확실히 저장하고 반복을 끝내기 위함입니다. m이 제수로 나누어 떨어지면 m을 제수로 나눈 다음 차수를 1씩 올리고 그렇지 않으면 일단 차수가 1 이상이면 (제수, 차수) 형태의 튜플로 배열에 저장하고 아니면 건너뛴 뒤 제수를 1씩 올리고 차수를 0으로 초기화합니다. 이렇게 해서 m이 1이 되고 마지막 소인수마저 배열에 저장되면 반복을 종료합니다.
18번 줄에서 소인수분해 결과 출력을 시작합니다. 먼저 입력값과 인수가 동일하면 ‘소수입니다’라는 결과를 출력, 아니면 소인수분해 결과를 (소인수, 차수) 형태의 튜플로 한 줄씩 출력합니다.
이 프로그램의 결과는 다음과 같습니다. 앞의 결과는 소수로 입력한 예, 뒤의 결과는 합성수로 입력한 예입니다.
2 이상의 자연수를 입력하세요: 73 소인수분해할 수는 73입니다. ★ 소인수분해 결과 ★ 73은(는) 소수입니다.
2 이상의 자연수를 입력하세요: 720 소인수분해할 수는 720입니다. ★ 소인수분해 결과 ★ 720은(는) 합성수입니다. ---- (2, 4) (3, 2) (5, 1) ----
용어설명
- 소수
- 약수가 1과 자기 자신 뿐인 수. (2, 3, 5, 7 등)
※참고: 1은 소수가 아님. 또한, 이 용어는 0과 1 사이의 실수를 의미하는 ‘소수’와 구별하기 위해 [소쑤]로 발음함. - 합성수
- 약수가 1과 자기 자신 외에 더 있는 수. (4, 6, 8, 9 등)
- 소인수분해
- 자연수를 소수들의 곱으로 나타내는 것.