[Python] 파이썬, 소인수 분해하기

소인수분해(Prime Factorization)란 다들 알다시피 1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것을 말한다. 소인수는 일단 1이라는 값이 아닌 2부터 시작하는 것이 핵심이며, 2로 나누지 못할 경우 2에서 +1를 해주면서 나누어지는지 체크하면 된다.

 

파이썬으로 소인수분해하기

 

소인수분해 소스코드

def factorization(x):
    d = 2

    while d <= x:
        if x % d == 0:
            print(d)
            x = x / d
        else:
            d = d + 1

factorization(9)    # 소인수 분해를 할 값을 입력한다.

# 결과
3
3

 

위 코드는 일단 소인수 분해를 할 값으로 9를 선택하였는데 결과는 당연히 3 x 3이 된다.