Naive Factorization Code

Pollard's Rho를 공부해보기 전에 직접 인수 분해 (소인수 분해) 알고리즘 코드를 작성해봤습니다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> getPrime(int n){
    vector<bool> isPrime(n, false);
    vector<int> ret;
    for(int i = 2; i <= n; i++){
        if(!isPrime[i]){
            ret.push_back(i);
            for(int j = i + i; j <= n; j += i){
                isPrime[j] = true;
            }
        }
    }
    return ret;
}

vector<int> factorization(int n){
    auto prime = getPrime(n);
    vector<int> ret;
    for(int i = 0; i < prime.size(); i++){
        if(n == 1) break;
        if(n % prime[i] == 0){
            while(n % prime[i] == 0){
                ret.push_back(prime[i]);
                n /= prime[i];
            }
        }
    }
    return ret;
}

int main(){
    int n;
    cin >> n;
    auto res = factorization(n);
    // n's factor
    for(auto factor : res) cout << factor << " ";
    return 0;
}