[백준][C++]11653번. 소인수분해

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

 

 

소인수분해를 하는 문제이다. 문제자체는 쉽기때문에 일단 풀고 어떻게 해야 시간복잡도를 줄일지 고민해보았다. 

일단 먼저 풀어본 방식은 순회를 하면서 나누어떨어지는게 있으면 벡터에 저장하고 전체를 순회했다면 벡터를

순회하면서 출력해주게 했다.

 

정답코드1

#include "iostream"
#include "vector"
#include "cma"

using namespace std;

int main()
{
	int n;
	vector<int> v;
	cin >> n;

	if (n == 1) cout << "" << endl;

	for (int i = 2; i <= n;)
	{
		if (n % i == 0)
		{
			n /= i;
			v.push_back(i);
		}
		else
		{
			i++;
		}
	}

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}


	return 0;
}

 

2번째 방식은 어떤 수 n이 a * b로 표현될 때, 적어도 하나의 인수는 sqrt(n) 이하인 것을 사용하여 주어진 수의 제곱근까지만 순회를 하는 방식으로 구현하였다.

 

정답코드2

#include "iostream"
#include "vector"
#include "cmath"

using namespace std;

int main()
{
	int n;
	vector<int> v;
	cin >> n;

	if (n == 1) cout << "" << endl;

	for (int i = 2; i <= sqrt(n); i++) {
		while (n % i == 0) {
			n /= i;
			v.push_back(i);
		}
	}

	// 남아있는 소수 `n`이 있다면 그것도 출력
	if (n > 1) {
		v.push_back(n);
	}

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}


	return 0;
}

 

3번째 방식은 에타토스테네스의 체를 이용하는 방식이다. 일단 범위내의 소수를 모두 구해두고 구한 소수를 통해 소인수분해를 하는 방식이다. 

 

정답코드3

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 에라토스테네스의 체를 이용하여 범위 내의 모든 소수를 구함
vector<int> sieve(int max) {
    vector<bool> is_prime(max + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= max; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= max; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

int main() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << "" << endl;
        return 0;
    }

    // 소수 리스트를 미리 구함
    int max_prime = sqrt(n);  // 소수를 구할 최대 범위 설정
    vector<int> primes = sieve(max_prime);

    // 소인수 분해 수행
    vector<int> factors;
    for (int prime : primes) {
        while (n % prime == 0) {
            factors.push_back(prime);
            n /= prime;
        }
    }

    // 남아있는 소수 n이 있으면 그것도 출력
    if (n > 1) {
        factors.push_back(n);
    }

    // 결과 출력
    for (int factor : factors) {
        cout << factor << endl;
    }

    return 0;
}