[백준 BOJ] 2312 수 복원하기

링크

https://www.acmicpc.net/problem/2312

 

풀이

 

2~100,000의 수를 소인수분해 하는 프로그램입니다.

저는 2~100,000까지의 소수를 구하고 그 소수들로 n을 1이 될 때까지 나누어 소인수 분해를 했습니다.

 

 

코드

//2312_수 복원하기
#include <cstdio>
#include <math.h>
using namespace std;

int arr[30000] = { 2 };
int T, n, cnt;

int main() {
	for (int i = 3; i <= 100000; i += 2) {	//소수 구하기
		int flag = 1;
		for (int j = 3; j <= sqrt(i);++j) {
			if (i%j == 0) {
				flag = 0;
				break;
			}
		}
		if (flag) arr[++cnt] = i;
	}

	scanf("%d", &T);

	while (T--) {
		scanf("%d", &n);

		for (int i = 0; i <= cnt; ++i) {	//소인수 분해
			int c = 0;
			while (!(n%arr[i])) {
				c++;
				n /= arr[i];
			}
			if(c!=0) printf("%d %d\n", arr[i], c);
			if (n == 1) break;
		}
	}

	return 0;
}