소인수분해 파이썬 - soinsubunhae paisseon

Question

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

목차 Show

소인수분해 소스코드
### 소인수 분해 ?
### 함수로 만든 소인수 분해 알고리즘
소인수 분해

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

소인수분해 소스코드

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이 된다.

무작정 따라하기 19-2

소인수분해를 하는 프로그램

◉ 예제 소스 19A-prime.py

# 소인수분해 프로그램

x = int(input("?")) # 소인수분해할 숫자를 입력받아 정수로 바꿉니다.

d = 2 # 가장 작은 소수인 2부터 나눕니다.

while d <= x:

if x % d == 0: # x가 d로 나누어지면(나머지가 0이면)

print(d) # d는 x의 약수이므로 출력합니다.

x = x / d # x를 d로 나눠서 다시 x에 저장합니다.

else:

d = d + 1 # 나누어지지 않으면 1을 더해서 반복합니다.

TIP

약수란 어떤 수를 나누어 떨어지게 하는 0이 아닌 정수를 의미합니다. 예를 들어 1은 모든 수의 약수이죠.

신간 소식 구독하기

뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.

안녕하세요

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

### 소인수 분해 ?

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

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()

소인수 분해

소인수 : 어떤 자연수의 인수(약수) 중에서 소수인 것
소인수 분해 : 1보다 큰 자연수를 소인수만의 곱으로 나타낸 것
ex) 45 = 3 x 3 x 5

소인수 분해 코드

def factorize(n):
    factor = 2      # 시작 값
    factors = []    # 소인수를 담을 리스트
    
    while (factor**2 <= n):           # n까지 확인하지않고 n의 제곱근까지 확인
        while (n % factor == 0):      # factor의 값이 n의 소인수이면 루프
            n = n // factor            # n의 값을 변경해준다.
            factors.append(factor)     # 소인수이기 때문에 리스트에 담는다.
        factor += 1         # 소인수가 아니면 루프를 빠져나와 factor의 값을 1더한다.
    
    if n > 1:
        factors.append(n)   # 루프를 다 돌고 n의 값이 더이상 나눠지지 않는데 n이 1보다 크면 그 값도 소인수이기 때문에 추가
    
    return factors

소인수 찾기

def findFactors(n):
    factor_list = factorize(n)   # 사전 제작한 factorize 함수 사용
    factors = []   # 소인수를 담을 리스트
    
    for i in factor_list:
        if (i not in factors):    # factors 리스트에 소인수 값이 없으면 추가
            factors.append(i)
            
    return factors

findFactors(3757208)

사전 제작한 함수를 불러오는 방법 말고 세트로 중복을 없애고 리스트로 바꿔서 값을 반환하는 방법도 있다.

def factorize(n):
    factor = 2      # 시작 값
    factors = []    # 소인수를 담을 리스트
    
    while (factor**2 <= n):           # n까지 확인하지않고 n의 제곱근까지 확인
        while (n % factor == 0):      # factor의 값이 n의 소인수이면 루프
            n = n // factor            # n의 값을 변경해준다.
            factors.append(factor)     # 소인수이기 때문에 리스트에 담는다.
        factor += 1         # 소인수가 아니면 루프를 빠져나와 factor의 값을 1더한다.
    
    if n > 1:
        factors.append(n)   # 루프를 다 돌고 n의 값이 더이상 나눠지지 않는데 n이 1보다 크면 그 값도 소인수이기 때문에 추가
    
    return list(set(factors)