[2321] 수 복원하기 - python 풀이

알고리즘 설계 기법

• 소인수분해 알고리즘

핵심은 "어떤 수 X를 소인수분해 하려면 X를 2부터 차례대로 X의 제곱근까지의 숫자로 나누어 떨어지는지 검사"하면 된다. 하지만 for문을 쓰면 쓸데없이 소스가 길어지기 때문에 while문을 활용해서 나눈 값이 0이면 출력하는 방식으로 프로그래밍 하는것이 효율적이다.

답

N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))

for i in T:
    k = 2
    count = 0
    while i != 1:
        if i % k == 0:
            i //= k
            count += 1
        else:
            if count != 0: print(k, count)
            k += 1
            count = 0
    if count != 0: print(k, count)

문제 풀러가기

2312번: 수 복원하기

해답을 얻은 곳 : https://agileflame.tistory.com/5