[백준/BOJ] 16536 어려운 소인수분해 - 접근과 풀이 (c++)

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

16563번: 어려운 소인수분해

Good Bye BOJ, 2021! B번 풀다가 폴라드 로 알고리즘으로 푸는줄 알고 헛수고하다가 복습 겸 찾아 본 소인수 분해 문제.

사실 소인수 분해 알고리즘을 잘 몰랐는데, 이 문제 때문에 소인수 분해 알고리즘을 좀 찾아봤다. 

 

 

 

싸지방에서 풀이 올리던 블로그에서 가져온 글 - 1

 

---

접근 방법

 

소인수 분해는 여러가지 방법으로 수행 가능하다. 그중에서 '에라스토테네스의 체' 분류에서 문제를 찾았다.

 

일반적인 소인수 분해 알고리즘은 1부터 √n까지의 수로 나눠보면 되므로 O(√n) 시간이 걸린다.

근데 이 문제에서 k의 값이 최대 500만이고, N이 최대 100만이므로 시간초과에 걸린다. 

 

그래서 생각한 방법이, √k 의 최댓값이 2237이고, 이 이하의 소수를 모두 구해서 벡터에 저장한다.

그리고 k를 가장 작은 소수부터 나누어 나가면서 출력한다. 

내가 생각한 시간 복잡도는 O( max( log2k,v.size())) 이고 v는 2237 이하의 소수를 담은 벡터이고, 대략 300개이다.

 

---

풀이

 

tag : math

#include <iostream>
#include<vector>
using namespace std;
int N;
vector<int> v;
int main() {
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  for(int i=2;i*i<=5000000;i++){
    int flag=0;
    for(int j=2;j*j<=i;j++){
      if(i%j==0){
        flag=1;
        break;
      }
    }
    if(flag==0)
      v.push_back(i);
  }

  for(int i=0;i<N;i++){
    int n;
    cin>>n;
    for(int j=0;j<v.size() && v[j]<=n;j++){
      while(n%v[j]==0){
        n=n/v[j];
        cout<<v[j]<<" ";
      }
    }
    if(n!=1) cout<<n;
    cout<<"\n";
  }
}