[C++] BOJ 11653 소인수분해

문제 출처

백준 온라인 저지

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

11653번: 소인수분해

 

문제 

 

입 / 출력

 

 

풀이

우선 에라스토테네스의 체로 소수를 구해준뒤 vector에 넣어준 뒤,

입력 받은 수가 0일 될 때까지 가능한 소수로 나누어 준 뒤

해당 소수들을 출력해서 해결할 수 있다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 10000001;
int arr[MAX] = {
    0,
};
int n;
vector<int> idx;
vector<int> result;
int main() {

  for (int i = 2; i < MAX; i++) {
    arr[i] = i;
  }

  for (int i = 2; i < MAX; i++) {
    if (arr[i] == 0)
      continue;
    for (int j = 2 * i; j < MAX; j += i) {
      arr[j] = 0;
    }
  }
  for (int i = 2; i < MAX; i++) {
    if (arr[i] != 0)
      idx.push_back(arr[i]);
  }

  cin >> n;

  for (int i = 0; i < idx.size();) {
    if (n == 0)
      break;
    if (n % idx[i] == 0) {
      result.push_back(idx[i]);
      n /= idx[i];
    } else
      i++;
  }
  for (int i = 0; i < result.size(); i++) {
    cout << result[i] << "\n";
  }
}