mojo's Blog
[백준 16563] 어려운 소인수분해 본문
문제 링크 => https://www.acmicpc.net/problem/16563
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 |