Boj16563_어려운 소인수분해

Published: December 04, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

boj16563_어려운 소인수분해

많은 수의 소인수분해.. 종만북!잘 보자

#include<iostream>

using namespace std;
int visit[5000001];//0이면 소수

int main() {
	for (int i = 2; i*i <= 5000001; i++) {
		if (!visit[i]) {
			for (int j = i * i; j < 5000001; j+=i) 
				if (!visit[j])
					visit[j] = i;
		}
	}
	int n, num;
	scanf("%d", &n);
	//n = 1000000;
	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		//num = 4999999;
		while (visit[num] != 0) {
			printf("%d ", visit[num]);
			num /= visit[num];
		}
		printf("\n");
	}
	return 0;
}