(파이썬) 소인수 분해

프로그래밍을 이용하여 수학문제를 풀때 의외로 소인수 분해를 해야할 일이 많아진다.

소인수 분해의 원리는 다들 잘 알고 있으리라 생각된다.

일단 소수들의 리스트를 만들어 놓고, 그것들을 하나씩 불러내서 소인수 분해 하고자 하는 수를 나누어 떨어지는 동안 계속 나눈다.

나누어 떨어지지 않게 되면 소수들의 리스트에서 다음 소수를 불러내 똑같은 작업을 반복한다. 이 작업을 몫이 1이 될때까지 계속한다.

예를 들어, 80을 소인수분해 하면 (몫, 소인수)가 다음과 같이 변해 갈 것이다.

(40, 2)

(20, 2)

(10, 2)

(5, 2)

이제 5는 2로 나누어 떨어지지 않으므로 3을 불러낸다. 그러나 5는 3으로도 나누어 떨어지지 않으므로 5를 불러낸다.

(1, 5)

이제 몫이 1이 되었으므로 소인수 분해를 멈추게 된다.

결과로는 [(2, 4), (5, 1)] 을 얻을 수 있다. 이것은 2가 4번 곱해지고 5가 1번 곱해지만 80이 된다는 의미이다.

코드는 다음과 같다.

from primetext import primelist
primenumber=primelist()   
# primenumber는 1000000개의 소수를 포함한 리스트임

def factor(n):
	result=[]
	for i in primenumber:
		count=0
		while n%i==0:
			count+=1
			n=int(n/i)
		if count!=0: 
			result.append((i, count))  
                        # (소수, 개수) 형태로 리스트에 추가됨
		if n==1:
			break
	return result

if __name__=="__main__":
	number=int(input("소인수 분해할 숫자를 입력하시오 : "))
	print(factor(number))

결과는 다음과 같다.

소인수 분해할 숫자를 입력하시오 : 3456
[(2, 7), (3, 3)]