[백준] 11653번: 소인수분해 - c++

소인수분해

문제

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

입력

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

출력

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

예제

문제 정의

처음엔 10,000,000 이하의 모든 소수를 저장한 배열을 만든다음 배열안의 원소를 돌려 소수이면 결과 배열에 저장했었다.

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> sosu;
vector<int> res;

bool is_prime(int num) {
  if (num < 2) return false;
  for (int j = 2; j * j <= num; j++) {
    if (num % j == 0) return false;
  }
  return true;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 2; i < 100; i++) {
    if (is_prime(i))
      sosu.push_back(i);
  }
  int tmp = n;
  while (true) {
    if (tmp == 1 || is_prime(tmp)) {
      if (is_prime(tmp))
        cout << tmp << "\n";
      return 0;
    }
    for (int i = 0; i < sosu.size(); i++) {
      if (tmp%sosu[i] == 0) {
        res.push_back(sosu[i]);
        cout << sosu[i] << "\n";
        tmp = tmp / sosu[i];
        break;
      }
    }
  }

  return 0;
}

하지만 이렇게 하다보니 is_prime(소수인지 확인하는 함수)를 자주 호출하게 되고 is_prime 내에 시간 복잡도가 크다 보니까 시간초과가 발생했다.

그래서 지피티의 힘을 빌렸다..

단순하지만 효율적인 코드를 받아볼 수 있었다.

먼저, 짝수를 처리하기 위해 2로 안나눠질때 까지 2로 나누고 출력을 한다.

그 후 3부터 n의 제곱근까지 반복문을 돌며 홀수만 나누고 출력한다.

그 후 n이 1보다 클 경우, 마지막으로 남은 소수를 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;

int n;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> n;
  if (n == 1) return 0;

  while (n % 2 == 0) {
    cout << 2 << "\n";
    n /= 2;
  }

  // 3부터 sqrt(n)까지 홀수만 나누기
  for (int i = 3; i * i <= n; i += 2) {
    while (n % i == 0) {
      cout << i << "\n";
      n /= i;
    }
  }

  // 마지막으로 남은 소수 출력
  if (n > 1) {
    cout << n << "\n";
  }

  return 0;
}

🔑🔑🔑 나와 다른 생각과 접근법으로 작성한 코드를 많이 접하는게 사고를 넓히는데 도움이 되는 것 같다.