백준 16563 - 어려운 소인수분해 (C++)

 

문제 그대로 주어진 숫자를 소인수분해하여 소인수를 오름차순으로 출력하면 된다.

 

 

문제 풀이

 

기본적인 아이디어는 모든 소인수는 소수라는 개념을 토대로 하였다.

 

먼저, 최대숫자가 500만이기 때문에, 500만 이하의 소수를 구하는 것이 먼저일 것이다.

소수를 구하는 알고리즘으로 에라토스 테네스의 체를 사용하였다.

모른다면 여기를 클릭하여 나오는 게시글을 참조하자.

 

하지만, 500만 이하의 소수를 모두 구하는 것은 사실 불필요하다.

왜냐하면,  숫자 N을 A * B로 표현한다면 둘 중 하나는 반드시 sqrt(N)보다 작기 때문이다.

(R은 N의 제곱근, A, B는 곱했을 때 N이 되는 N의 약수)

 

$$ N = R * R $$

$$ N = A * B $$

$$ R * R = A * B $$

 

만약, A가 R보다 크다면 아래의 모순이 발생

$$ R * R < A * B $$

 

즉, B가 R보다 작은 값이어야지만 R * R = A * B 의 관계에 모순이 생기지 않는다.

 

B가 R보다 크더라도 마찬가지의 관계가 성립되므로

A와 B중 하나는 반드시 R보다 작은 값이어야 한다.

 

sqrt(N)이하의 소수를 모두 구했다면, 두 가지 경우를 생각해볼 수 있다.

 

1. N의 소인수가 모두 sqrt(N)보다 작은 경우

2. N의 소인수에 sqrt(N)보다 큰 소인수가 포함되어있는 경우

 

1번 경우를 생각해보자.

N의 소인수가 모두 sqrt(N)보다 작다면 N을 나누었을 때 나머지가 0이되는 수를 sqrt(N)이하의 소수에서 찾아 계속 N을 나누어준다면 N은 최종적으로 모든 소인수를 제거하고 1이 될 수 있다.

소인수가 하나씩 제거될 때 마다 해당 소인수를 출력해준다면, 답을 구할 수 있다.

 

2번 경우를 생각해보자.

N의 소인수중에서 sqrt(N)보다 큰 소인수가 포함되어 있다면, sqrt(N)이하의 소수들로 N을 아무리 나누어도 N은 1이 되지 않는다. sqrt(N) 보다 큰 소인수가 나누어지지 않기 때문이다.

 

N을 sqrt(N)이하의 소수들중 나머지가 0이되는 수로 계속 나누었을 때, N이 M이 되었다고 해보자.

이 M은 sqrt(N)보다 큰 수이다. 

 

여기서 다시 두 가지 경우를 따져보자.

 

1. M이 소수인 경우

2. M이 합성수인 경우

 

M이 소수라면, 그냥 마지막에 함께 출력해주면 된다.

M은 N의 소인수이기 때문이다.

 

M이 합성수라면, M이 소수가 될 때 까지 계속 나누어주어야 한다.

그런데 M이 합성수일 수 있을까?

 위에서 숫자 N을 두 수의 곱으로 표현한다면 둘 중 하나는 반드시 sqrt(N)보다 작아야 한다고 했다.

 

즉, M이 합성수라면 M의 소인수에도 반드시 sqrt(M)보다 작은 부분이 포함되어 있어야 한다.

하지만, sqrt(M) < sqrt(N) 이므로 N을 나누는 과정에서 M의 소인수는 모두 제거될 수 밖에 없다.

(N이 더이상 나누어지지 않을 때까지 나누었기 때문에)

 

고로 M은 반드시 소수이다.

 

결과적으로 마지막에 남은 M이라는 숫자가 1이 아니라면, M을 추가적으로 출력해주면 끝이다.

 

이해가 안된다면 코드를 보며 다시 이해해보자.

 

풀이코드

 

int NumSize = 0;
std::cin >> NumSize;

std::vector<int> Nums(NumSize);
for (int i = 0; i < NumSize; i++)
{
    std::cin >> Nums[i];
}

 

먼저, 소인수를 구해야 하는 숫자들을 입력받고 저장해주자.

int MaxSize = std::sqrt(5000000);

std::vector<int> AllNumbers(MaxSize + 1, 0);
AllNumbers[1] = -1;

for (int i = 2; i <= MaxSize; i++)
{
    if (AllNumbers[i] == -1)
    {
        continue;
    }

    for (int j = i * 2; j <= MaxSize; j += i)
    {
        AllNumbers[j] = -1;
    }
}

 

에라토스 테네스의 체 알고리즘을 이용하여, sqrt(5000000)이하의 소수를 모두 구해주었다.

std::vector<int> PrimeNumbers;
PrimeNumbers.reserve(MaxSize);

for (int i = 1; i <= MaxSize; i++)
{
    if (AllNumbers[i] == 0)
    {
        PrimeNumbers.push_back(i);
    }
}

 

소수만 저장할 벡터를 따로 선언하여, 소수만 옮겨주었다.

 

std::vector<int> Answers;
Answers.reserve(NumSize);

for (int i = 0; i < NumSize; i++)
{
    int TargetNumber = Nums[i];

    for (int j = 0; j < PrimeNumbers.size(); j++)
    {
        if (TargetNumber % PrimeNumbers[j] == 0)
        {
            TargetNumber /= PrimeNumbers[j];
            Answers.push_back(PrimeNumbers[j]);
            j--;
        }

        if (TargetNumber <= 1)
        {
            break;
        }
    }

    if (TargetNumber > 1)
    {
        Answers.push_back(TargetNumber);
    }

    for (int j = 0; j < Answers.size(); j++)
    {
        std::cout << Answers[j] << " ";
    }

    std::cout << "\n";

    Answers.clear();
}

 

먼저, 출력할 소인수들을 저장해줄 Answer벡터를 선언하였다.

이후, 소인수를 구할 숫자들의 수만큼 반복문을 돌며 각 숫자들의 소인수를 구해주었다.

 

소인수를 구하는 방법은 간단하다.

소수만 모아둔 벡터의 원소들로 숫자를 계속 나누어주었다.

 

하지만, 주의해야 하는 점은 숫자가 같은 소수로 여러번 나누어 질 수 있다는 것이다.

64의 경우, 2 * 2 * 2 * 2 * 2 * 2 이다.

즉, 같은 소수가 소인수에 여러 번 포함될 수 있다는 것이다.

 

그렇기 때문에 중간의 코드를 보면 j-- 를 해주고 있다.

다음 인덱스로 넘어가지 않고 동일한 숫자로 다시 나누어보는 것이다.

 

그렇게, 숫자를 나누어보면서 나누어지는 소수들을 Answer벡터에 넣어주었다.

마지막에 남은 TargetNumber가 1보다 큰 숫자라면 해당 숫자도 Answer벡터에 삽입해주었다.

 

마지막으로 Answer의 원소를 모두 출력해준 뒤, Answer를 재사용하기 위해 clear해주었다.