소인수분해

난 일케 함.

 

#include <string>
#include <vector>

using namespace std;

//에라토스테네스의 체

vector<int> solution(int n) {
    vector<int> answer;
    vector<bool>  isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
  
    for (int i = 2; i * i <= n; ++i) //i는 2부터 시작하여 모든 수를 소수라 가정
    {
        if (isPrime[i])
        {
            if (n % i == 0) //약수
                answer.push_back(i);

            for (int j = i * i; j <= n; j += i) //소수 i의 배수는 합성수
            {
                isPrime[j] = false;
            }
        }
    }

    return answer;
}

 

아니, i*i하면 n이 소수인 경우, 안나와서 i=n으로 변경했고 비효율적임.

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    int i = 2;

    while (n >= i * i) {
        if (n % i == 0) {
            answer.push_back(i);
            n /= i;
        } else {
            i++;
        }
    }
    if (n > 1) {
        answer.push_back(n);
    }
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    return answer;
}

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;

    while (n % 2 == 0) {
        answer.push_back(2);
        n /= 2;
    }

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

    if (n > 1) {
        answer.push_back(n);
    }

    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    return answer;
}