mojo's Blog

[백준 16563] 어려운 소인수분해 본문

백준/etc

[백준 16563] 어려운 소인수분해

_mojo_ 2021. 7. 22. 15:09

문제 링크 => https://www.acmicpc.net/problem/16563

 

16563번: 어려운 소인수분해

첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다.

www.acmicpc.net


2~5,000,000 범위의 숫자들이 1~1,000,000 개가 주어질때 각각의 숫자들을 소인수분해하여 소인수들을 오름차순으로 출력하는 문제이다.

 

우리가 일반적으로 알고있는 factorize 의 시간복잡도는 O(N^(1/2)) 이므로 대략 5,000,000의 루트에 1,000,000을 곱한다면 2,236,067,977.499789... 이므로 시간초과가 난다는 것은 확실하다.

 

따라서 이를 해결하기 위해서 에라스토테네스의 체를 활용하는 것이다.

 

다음과 같이 1차원 배열 p 에다가 에라스토테네스의 체와 동일하게 값을 채우도록 한다.

int p[5000001];

void sieve() {
	for(int i=2; i<=5000000; i++) p[i]=i;
	for(int i=2; i<=5000000; i++) {
		if(p[i]==i) {
			for(int j=i+i; j<=5000000; j+=i) {
				p[j]=i;
			}
		}
	}
}

이때 중요한 것은 소수일때 p[i] = i 라는것이다.

 

그렇다는 의미는 소수가 아닐 때 p[i] != i 라는 것이며 p[i] = i 일 때 p[j] = i 를 채워준다는 의미는 소수 i 의 2,3,4,... 배수가 전부 i로 채워진다는 것이다.

 

45의 소인수를 구하는 것을 예로 들어보도록 하자.

 

p[45] 의 값을 유추해 보면 3임을 알 수 있다. (소수 3에 대하여 p[3] == 3 이므로 3의 배수들 전부 3으로 채워짐)

 

따라서 소인수가 3임을 알 수 있으므로 15(45 / p[45])의 소인수를 구해야 한다. 

 

p[15] 의 값 또한 유추해 보면 3임을 알 수 있다.

 

따라서 소인수가 3임을 알 수 있으므로 5(15 / p[15]) 의 소인수를 구해야 한다.

 

p[5] 의 값은 5 자체가 소수이므로 5임을 알 수 있다.

 

따라서 소인수가 3 => 3 => 5 순서로 나오는 것을 알 수 있다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int p[5000001];

void sieve() {
	for(int i=2; i<=5000000; i++) p[i]=i;
	for(int i=2; i<=5000000; i++) {
		if(p[i]==i) {
			for(int j=i+i; j<=5000000; j+=i) {
				p[j]=i;
			}
		}
	}
}

vector<int> factorize(int x) {
	vector<int> res;
	while(x!=1) {
		res.push_back(p[x]);
		x/=p[x];
	}
	sort(res.begin(), res.end());
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	sieve();
	int n;
	cin>>n;
	for(int i=0; i<n; i++) {
		int x;
		cin>>x;
		vector<int> v = factorize(x);
		for(int i=0; i<v.size(); i++) {
			cout<<v[i]<<" ";
		}
		cout<<endl;
	}
		

	return 0;
}

'백준 > etc' 카테고리의 다른 글

Extended Euclidean Algorithm  (0) 2021.07.22
[백준 1222] 홍준 프로그래밍 대회  (0) 2021.07.22
에라스토테네스의 체  (0) 2021.07.22
소인수분해 하는 방법  (0) 2021.07.22
[백준 4256] 트리  (0) 2021.07.18
Comments