구리 개발소

문제:

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력:

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

풀이:

소인수분해 문제를 해결하기 위해서는 우선 소수를 판정하는 방법에 대해 알아야한다.

어떤 수 $x$가 소수일 조건은 약수로 1과 자기 자신만을 가져야 한다. 따라서 $x$를 $[2, x - 1]$ 범위 내의 수로 나누었을때, 나누어 떨어지는 수가 없으면 그 수는 소수이다. 이를 코드로 표현하면 다음과 같다.

bool IsPrime(int x) {
    for (int i = 2; i < x; ++i) {
        if (x % i == 0)
            return false;
    }
    return true;
}

위 알고리즘의 시간복잡도는 $O(x)$이다. 이 시간복잡도를 줄일 수가 있는데 이론은 다음과 같다.

bool IsPrime(int x) {
    for (int i = 2; i*i <= x; ++i) {
        if (x % i == 0)
            return false;
    }
    return true;
}

이를 통해 우린 시간복잡도를 $O(\sqrt{x})$로 줄일 수 있다.

소수를 판정하는 대표적인 방법으로는 에라토스테네스의 체가 있다. 에라토스테네스의 체는 1과 자기자신 사이에 약수의 배수를 모두 지우면 남는 수가 약수라는 이론이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

이제 이를 활용해 문제를 풀어보도록 하자.

예를 들어, $72$가 있으면 $2*2*2*3*3$으로 표현된다. 이를 살펴보면 2로 가능한 나누어 표현하고 그 다음으로 3으로 가능한 나누어 표현하였다.

따라서 우리는 어떤 수 $x$에 대해 작은 수부터 가능할 때까지 나누어주며 그 수를 출력해주면 된다. 범위는 앞선 알고리즘에서 살펴본 바로 $[2, \sqrt{x} - 1]$ 까지로 하면 된다. 결과적으로 2의 배수, 3의 배수, 5의 배수...가 차례대로 지워지면서 소인수들이 갯수만큼 출력이 된다.

#include <iostream>
using namespace std;

void __init() {
  cin.tie(0);
  ios::sync_with_stdio(0);
}

void Factorization(int num) {
  for(int i = 2; i*i <= num; i++) {
    while(num % i == 0) {
      cout << i << "\n";
      num /= i;
    }
  }
  if(num != 1) cout << num;
}

int main() {
  int num;

  __init();

  cin >> num;
  Factorization(num);
}