문제
양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.
출력
각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.
예제 입력 1
2 6 24 |
예제 출력 1
2 1 3 1 2 3 3 1 |
더보기
Solution
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
bool isPrime(int N)
{
if(N<2)
return false;
else if(N==2)
return true;
else if(N%2==0)
return false;
else
for(int i=3;i*i<=N;i+=2)
if(N%i==0)
return false;
return true;
}
int main(void)
{
int test_case;
scanf("%d", &test_case);
for(int t=0;t<test_case;t++)
{
int N, *fac=NULL, temp;
scanf("%d", &N);
fac=(int *)calloc(N+1,sizeof(int));
temp=N;
for(temp=2;temp<=N;temp++)
if(N%temp==0)
if(isPrime(temp))
{
fac[temp]++;
N/=temp;
temp--;
}
if(N!=1)
fac[N]++;
for(int i=2;i<=temp;i++)
if(fac[i]!=0)
printf("%d %d\n", i, fac[i]);
free(fac);
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 2485번: 가로수 (0) | 2020.12.22 |
---|---|
<백준 알고리즘> 3049번: 다각형의 대각선 (0) | 2020.12.22 |
<백준 알고리즘> 5618번: 공약수 (0) | 2020.12.22 |
<백준 알고리즈> 4796번: 캠핑 (0) | 2020.12.22 |
<백준 알고리즘> 2935번: 소음 (0) | 2020.12.22 |