[Silver III] 수 복원하기 - 2312

문제 링크

성능 요약

메모리: 34536 KB, 시간: 1652 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체, 소인수분해

제출 일자

2025년 5월 20일 23:03:58

문제 설명

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

출력

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

---

💡 해결 방법

💻 코드

from math import ceil
 
n = int(input())
nums = [int(input()) for _ in range(n)]
 
 
 
 
 
 
 
 
for num in nums:
    record = []
    for x in range(2, num + 1):
        target = num
        ans = 0
        if num % x == 0 and all((x  % recordnum) != 0 for recordnum in record):
            record.append(x)
            while target % x == 0:
                ans += 1
                target = target // x
 
            # print(record)
            print(x, ans)