문제:
양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.
입력:
첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2<=N<=100,000)이 주어진다.
출력:
각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.
풀이 방법:
소인수분해는 말 그대로 소수로만 분해가 된다. 따라서 2부터 시작해서 n이 1이 될 때까지 소수로 나눠주면 된다. 소수인지 따로 판별이 필요하지 않다.(이전에서 이미 다 나눠버렸기 때문에) 따라서 각 count별로 answer를 계산하고 더 이상 나눠주지 못한다면 초기화를 하고 다음으로 넘어가면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
for i in range(int(input())):
n=int(input())
count=2
answer = 0
while n!=1:
if n%count==0:
n//=count
answer+=1
else:
if answer==0:
pass
else:
print(count,answer)
answer=0
count+=1
print(count,answer)
|
cs |
문제 링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1309. 동물원 (0) | 2019.08.05 |
|---|---|
| [BOJ]5430. AC (0) | 2019.08.04 |
| [BOJ]15649. N과M(1),(2) (0) | 2019.08.02 |
| [BOJ]1009. 분산처리 (0) | 2019.08.01 |
| [Programmers]Lv 3.배달 (3) | 2019.07.31 |