[Python] 소인수분해 프로그램 만들기

 중학교 1학년만 다니셨으면 모두 아시겠지만, 소인수분해란, 어떠한 수를 소수인 인수로 분해한 곱으로 나타내는 겁니다.

 

 소수(素數)는 약수를 자기 자신과 1만 갖는 수를 말하고, 인수(因數)는 정수 또는 정식을 몇 개의 곱의 꼴로 하였을 때에, 그것의 각 구성요소를 이르는 말... 인데! 그냥 약수라고 생각해 주시면 됩니다.

 

 그러니까 어떤 수를 소인수분해한다 함은 그 수의 약수 중 소수를 골라 그의 곱으로 나타내는 것이죠.

 

 

 위 그림이 소인수분해의 원리인데, 가장 작은 소수로 계속 나누어서 마지막 소수가 나올 때까지 나누고, 나눈 소수를 곱으로 연결해주는 것이죠. 위 그림의 64는 2 * 2 * 2 * 2 * 2 * 2 이니 2^6으로 나타낼 수 있겠죠.

 

 다른 예를 들어 볼까요? 18을 소인수분해한다고 하면 2가 하나, 3이 두개이니 2^1 * 3^2 로 나타낼 수 있습니다.

 

 그럼 이렇게 소인수분해를 하는 코드를 작성해보면... 

 

def soinsubunhe(su):
    sosu = []
    for i in range(2, su+1):
        yaksu = []
        for j in range(1, i+1):
            if len(yaksu) > 2:
                break
            if i % j == 0:
                yaksu.append('hihi')
        if len(yaksu) == 2:
            sosu.append(i)
    if su in sosu:
        return "이 수는 소수입니다."
    soinsubunhae = []
    i = 0
    while True:
        if su in sosu:
            soinsubunhae.append(su)
            break
        if su % sosu[i] == 0:
            soinsubunhae.append(sosu[i])
            su = su // sosu[i]
            i = 0
            continue
        i += 1
    re = []
    while True:
        if len(soinsubunhae) == 0:
            break
        first = soinsubunhae[0]
        sutja = soinsubunhae.count(first)
        re.append(str(first) + "^" + str(sutja))
        for i in range(sutja):
            if soinsubunhae[0] == first:
                del soinsubunhae[0]
            else:
                break
    return " * ".join(re)

su = int(input("소인수분해할 수를 입력하세요: "))
soinsu = soinsubunhe(su)
print("\n")
print(soinsu)

 

 

 하하... 제가 아무런 참고자료 없이 처음에 짠 코드입니다.

 

 우선 입력받은 수까지의 소수를 구하고, 입력받은 수를 소인수분해한 뒤에 a^b*c^d... 의 꼴로 나타내는 과정을 거치는데요.

 

 굉장히 긴 데다가 시간도 오래걸리고 아름답지도 않고 제가 짰지만 딱히 예쁜 코드는 아니라고 생각됩니다.

 

 그래서 구글에 다른 사람들이 짠 코드를 찾아봤는데...! 너무 좋은 코드들이 많은 겁니다.

 

 그 중 블로거 네오가 필요해님의 코드를 보면 엄청나게 간결하고 예쁘고 좋은 코드가 있어 가져와봅니다.

 

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

 

 엄청납니다... 입력받은 수를 2부터 시작해서 쭉 나누어 나누어떨어지는걸 print()하는 코드인데요... 저는 언제쯤이면 이렇게 예쁜 코드를 짜볼수 있을까요...

 

 그래서 제 코드의 출력방식과 위 코드를 합쳐보면:

 

def soinsubunhe(x): 
    d = 2 
    factorization = []
    while d <= x: 
        if x % d == 0: 
            factorization.append(d)
            x = x / d 
        else: 
            d = d + 1
    re = []
    while True:
        if len(factorization) == 0:
            break
        first = factorization[0]
        sutja = factorization.count(first)
        re.append(str(first) + "^" + str(sutja))
        for i in range(sutja):
            if factorization[0] == first:
                del factorization[0]
            else:
                break
    return " * ".join(re)
        
su = int(input("소인수분해할 수를 입력하세요: "))
soinsu = soinsubunhe(su)
print("\n")
print(soinsu)

 

 

 이런 코드가 나옵니다...!

 

 저도 코드를 간결하고 예쁘게 짜고 싶네요... 네오가 필요해님 존경합니다!