[백준] 17103 골드바흐 파티션 with C++

문제설명

---

입출력 예제

---

개념

　주어진 정수 N(짝수)을 두 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제다. 예를 들어, 10을 입력하면 10 = 3 + 7, 5 + 5로 2개가 출력된다. 이때 소수의 순서만 다른 것은 같은 파티션인 것에 유의하자.

 

　문제의 시간 제한이 매우 빡빡하기 때문에, 에라토스테네스의 체 알고리즘을 사용하여 주어진 범위 내의 소수를 미리 구한 후, 구한 소수들을 활용하여 문제를 해결할 수 있다. 이러한 알고리즘은 시간 복잡도가 O(Nlog(log(N))) 으로 매우 빠르다.

---

 

풀이

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

const int n = 1000000;
vector<bool> isprime(n + 1, true);

int main()
{
    SetPrime();
    int N, n;
    cin >> N;

　전역 변수로 에라토스테네스의 체를 초기화할 벡터 isPrime을 초기화한다. 이때 벡터의 크기는 문제에서 주어진 입력의 최댓값인 1,000,000으로 설정한다.

 

void SetPrime()
{
    for (int i = 2; i * i <= n; i++)
    {
        if (!isprime[i])
            continue;

        for (int j = i * i; j <= n; j += i)
            isprime[j] = false;
    }
}

　2부터 1,000,000까지 소수를 판별하여 isPrime에 삽입한다. 이때 초기화 과정에서 모든 숫자를 소수로 가정하여 true로 초기화하였기 때문에, 소수가 아닌 숫자들을 false로 바꿔주게 하였다.

 

	while (N--)
	{
    	    int count = 0;
            cin >> n;
            vector<int> v;
        
            for (int i = 2; i < n; ++i)
            {
            	if (isPrime[n])
                    v.push_back(i);
            }

　주어진 범위 내의 소수를 판별하여 벡터 v에 삽입한다.

 

        for (auto it = v.begin(); it != v.end(); ++it)
        {
            int other = n - *it;

            if (other < *it)
                break;

            if(binary_search(it, v.end(), other))
                count++;
        }

        cout << count << '\n';
    }
}

　에라토스테네스의 체 알고리즘을 사용해 n이하의 모든 소수를 구한 후, 구해진 소수들 중 두 개를 더해 n을 만들 수 있는 경우의 수를 찾는 것이다. 즉, 현재 원소 *it과 n - *it을 더해 n을 만들 수 있는 지를 판별하고 있다.

 

　만약 n - *it < *it이라면 이미 검사한 소수의 합으로 n을 만들어봤기 때문에, 더 이상 검사할 필요가 없으므로 break로 반복문을 탈출한다. 그렇지 않으면 나머지 소수들 중에 n - *it을 찾아서 count를 늘린다.

 

총합본

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

const int n = 1000000;
vector<bool> isprime(n + 1, true);

void SetPrime()
{
    for (int i = 2; i * i <= n; i++)
    {
        if (!isprime[i])
            continue;

        for (int j = i * i; j <= n; j += i)
            isprime[j] = false;
    }
}

int main()
{
    SetPrime();
    int N, n;
	cin >> N;

	while (N--)
	{
        int count = 0;
		cin >> n;
        vector<int> v;

		for (int i = 2; i < n; i++)
		{
            if (isprime[i])
                v.push_back(i);
		}

        for (auto it = v.begin(); it != v.end(); ++it)
        {
            int other = n - *it;

            if (other < *it)
                break;

            if(binary_search(it, v.end(), other))
                count++;
        }

        cout << count << '\n';
	}
}