c++ 에라토스테네스의 체를 이용한 빠른 소인수 분해

에라토스테네스의 체를 이용한 소인수 분해 코드입니다.

/*

에라토스테네스의 체를 이용한 빠른 소인수 분해

*/

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

 

const int MAX = 1000000;

 

int N; //소인수분해하고자 하는 수

//minFactor[i]=i의 가장 작은 소인수(i가 소수인 경우 자기 자신)

int minFactor[MAX];

 

//에라토스테네스의 체를 수행하면서 소인수분해를 위한 정보 저장

void eratosthenes(void)

{

        //1은 항상 예외 처리

        minFactor[0] = minFactor[1] = -1;

        //모든 숫자를 처음에는 소수로 표시

        for (int i = 2; i <= N; i++)

               minFactor[i] = i;

        //에라토스테네스의 체를 수행

        int sqrtN = int(sqrt(N)); //루트 N

        for (int i = 2; i <= sqrtN; i++)

               if (minFactor[i] == i)

                       for (int j = i*i; j <= N; j += i)

                              //아직 약수를 본 적 없는 숫자인 경우 i를 써둔다

                              if (minFactor[j] == j)

                                      minFactor[j] = i;

}

 

//2 이상의 자연수 N을 소인수 분해한 결과를 반환

vector<int> factor(void)

{

        vector<int> result;

        //N이 1이 될 때까지 가장 작은 소인수로 나누기를 반복

        int copy = N; //복사

        while (copy > 1)

        {

               result.push_back(minFactor[copy]);

               copy /= minFactor[copy];

        }

        return result;

}

 

int main(void)

{

        while (cin >> N)

        {

               cout << N << " = ";

               eratosthenes();

               vector<int> result;

               result = factor();

               for (int i = 0; i < result.size() - 1; i++)

                       cout << result[i] << " * ";

               cout << result[result.size() - 1];

               cout << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략