[알고리즘] 백준 11653번 "소인수분해" (C/C++) - Don 임베디드

문제요약:

자연수 N이 주어졌을 때, 소인수 분해 한 소수들을 오름차순으로 나열하라.

 

제약:

제한시간 1초, 메모리 256MB,

1 <= N <= 10,000,000

 

예제 1 입력.	예제 1 출력.
72	2 2 2 3 3
예제 2 입력.	예제 2 출력.
3	3
예제 3 입력.	예제 3 출력.
6	2 3
예제 4 입력.	예제 4 출력.
9991	97 103

 

정답 코드:

#include <iostream>
 
using namespace std;
 
// 각 자연수가 소수인지 여부를 저장할 boolean 배열.
bool bIsPrime[10000001];
 
void _SetPrime(int nSize);    // bIsPrime을 초기화 할 함수
void _PrintPrimes(int N);        // 소인수 분해 하여 출력할 함수.
 
int main()
{
    int N;
 
    // bIsPrime 초기화. 에라토스테네스의 체.
    _SetPrime(10000000);
 
    // 문제에서 주어지는 입력값.
    cin >> N;
 
    // 입력값에 따라 소인수 분해 결과를 출력. 
    _PrintPrimes(N);
 
    return 0;
}
 
void _SetPrime(int nSize)
{
    // Init bIsPrime Values
    bIsPrime[1] = false;
    for (int i = 2; i <= nSize; i++)
    {
        bIsPrime[i] = true;
    }
 
    // 에라토스테네스의 체. 소수인지 여부를 확인 후 저장.
    for (int j = 2; j <= nSize; j++)
    {
        if (bIsPrime[j] == false)    
        {
            // 대상 (i)가 소수가 아닌 경우 다음으로 넘어감.
            continue;
        }
 
        // 대상 (i)가 소수인 경우, 해당 소수의 모든 배수를 "소수가 아님" 표시.
        for (int k = (2 * j); k <= nSize; k += j)
        {
            bIsPrime[k] = false;
        }
    }
}
 
void _PrintPrimes(int N)
{
    // 입력받은 N.
    int nTmp = N;
 
    // 2부터 N 까지 loop을 돌면서 확인.
    for (int i = 2; i <= N; i++)
    {
        if (bIsPrime[i] == false)
        {
            // 소수가 아닌 경우 소인수 분해 X.
            continue;
        }
        
        // 소수인 경우, nTmp가 1이 될때까지 Loop를 수행.
        while (nTmp > 1)
        {
            // nTmp가 (i)로 나누어 떨어지는 경우
            if ((nTmp % i) == 0)
            {
                // 소수 (i)를 한번 출력 후
                cout << i << endl;
                // nTmp를 i로 나눈 수로 nTmp를 업데이트.
                nTmp /= i;
            }
            else
            {
                //나누어 떨어지지 않은 경우 다음 소수 (i)를 구하러 나감.
                break;
            }
        }
    }
}

원본 링크: https://www.acmicpc.net/problem/11653