Process

• 2부터 시작하여
• N이 그 소수로 나뉘는지 확인 (소인수인지 판단)
• 소인수로 판단된 경우 그 소수로 N을 나눠지지 않을 떄까지 나눈다.
• 몇 번 나눴는지를 cnt로 기록한 후,
• 더이상 나눠지지 않으면 그 소인수와 cnt를 기록
• 위 과정을 2 ~ n까지 반복

Point

여기서 N을 나누는 수가 소수인지 따로 판단하는 소수 판별 알고리즘이 필요가 없다.
가장 작은 소수인 2부터 n까지의 수들을 N을 나눌 수 있을 때까지 나누기 떄문이다.
그렇게 나누면 소수가 아닌 값으로 N을 나눌 수 없기 때문이다.
가령 N=12라고 할 때, 차례로 2로 2번 (12 -> 3), 3으로 1번 (3 -> 1) 나눌 것이기 때문에
4나 6 같이 소수가 아닌 수들로 나눠질 수 없고 결과적으로 고려하지 않고 넘어간다.
소수이지만 인수가 아닌 수들도 마찬가지이다.
위 예시에서 5, 7 같은 경우 나눠지지 않기에 넘어가진다.
그래서 소수 판별 알고리즘이 따로 필요 없다.

코드

import sys

input = sys.stdin.readline

def factorization(n):
     prime_cnt = []
     for p in range(2, n + 1):
          cnt = 0
          while n % p == 0:
               cnt += 1
               n = n // p
          if cnt:
               prime_cnt.append([p, cnt])
     for p in prime_cnt:
          print(*p)
               
                         

if __name__ == '__main__':
     t = int(input())
     for _ in range(t):
          factorization(int(input()))