<백준 알고리즘> 2312번: 수 복원하기

문제

양의 정수 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;
}