[SWEA-1945][Python] 간단한 소인수분해

문제

숫자 N은 아래와 같다.

$N=2^a \times 3^b \times 5^c \times 7^d \times 11^e$

N이 주어질 때 a, b, c, d, e 를 출력하라.

 

제약 사항

N은 2 이상 10,000,000 이하이다.

 

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N 이 주어진다.

 

출력

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

예제

[입력]	[출력]
10   6791400 1646400 1425600 8575 185625 6480 1185408 6561 25 330750	#1 3 2 2 3 1 #2 6 1 2 3 0 #3 6 4 2 0 1 #4 0 0 2 3 0 #5 0 3 4 0 1 #6 4 4 1 0 0 #7 7 3 0 3 0 #8 0 8 0 0 0 #9 0 0 2 0 0 #10 1 3 3 2 0

 

문제 해결 방법

• for 문을 이용하여 일일히 나누는 방식으로 문제를 해결하였다.
• 나눠질 때마다(@N % div == 0@) 해당 @answer@ 배열의 인덱스에 있는 값을 @1@씩 증가시켜주었다. 

num_list = [2, 3, 5, 7, 11]
answer = [0, 0, 0, 0, 0]

while N != 1:
    for idx, div in enumerate(num_list):
        if N % div == 0:
            answer[idx] += 1
            N = N // div

 

코드

T = int(input())

for test_case in range(1, 1 + T):
    N = int(input())

    num_list = [2, 3, 5, 7, 11]
    answer = [0, 0, 0, 0, 0]

    while N != 1:
        for idx, div in enumerate(num_list):
            if N % div == 0:
                answer[idx] += 1
                N = N // div
    
    print(f"#{test_case}", end=' ')
    print(' '.join(str(item) for item in answer))

 

참고

• 난이도: D2

 

소인수 분해 알고리즘

def prime_factors(n):
    factors = []
    # 2로 나누어 떨어지는 동안 나눔
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    # 3부터 시작하여 홀수 소수로 나눔
    for i in range(3, int(n**0.5) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    
    # n이 소수인 경우
    if n > 2:
        factors.append(n)
    
    return factors

 

참고 사이트

[Algorithm] 소인수 분해(Prime/Integer Factorization)