[Python] 소인수 분해하기

안녕하세요

 

파이썬으로 소인수를 분해하는 코드를 작성해보았습니다.

 

### 소인수 분해 ?

 

     합성수를 소수의 곱으로 나타내는 것입니다.

 

      6 합성수는 2 x 3

          18 합성수는 2 x 3 x 3 

          51  합성수는 3 x 17  

 

위 예시와 같이 소수로만 나타내는 작업입니다.

 

def get_prime_factor(num):
    from collections import defaultdict
    dic=defaultdict(int)
    d=2
    
    while d<=num:
        if num%d==0:
            dic[d]+=1
            num=num/d
        else:
            d+=1    
    return dic

print(get_prime_factor(6).items())
print(get_prime_factor(18).items())
print(get_prime_factor(51).items())

 

defaultdic : int형을 기본값으로 갖는 사전형을 만들기 위해 사용합니다.

나누는 초기값은 소수중 가장 작은 수 2입니다.

 

연산 접근 방법은 나머지가 0이면 딕셔너리의 값을 1올립니다.

이때, defaultdic을 사용해서 key값이 존재하지 않는다면 알아서 새로 생기게 됩니다.

 

만약 나머지가 0이 아니면 나누는수 d를 1증가 시킵니다.

 

해당 연산을 계속 수행하다가 나누는 수가 나눌 수보다 커진다면, while문을 빠져나오게 됩니다.

 

함수는 defaultdict 객체를 반환하게 됩니다.

 

리턴받은 객체는 다음과 같이 나타내어 확인할 수 있습니다.

dic=get_prime_factor(18)
prime=[]

for i in dic.keys():
    for j in range(dic[i]):
        prime.append(str(i))
bond=' x '

print('18 : ',bond.join(prime))

 

 

 

### 함수로 만든 소인수 분해 알고리즘

def get_prime_factor():
    from collections import defaultdict
    dic=defaultdict(int)
    num=int(input('소인수 분해할 수를 입력하세요 : '))
    d=2
    
    while d<=num:
        if num%d==0:
            dic[d]+=1
            num=num/d
        else:
            d+=1
        
    prime=[]

    for i in dic.keys():
        for j in range(dic[i]):
            prime.append(str(i))

    print('소인수 분해 결과입니다.')
    return print('18 : ',' x '.join(prime))

get_prime_factor()