[9020] 백준 : 골드바흐의 추측(C++)

 

* 접근 방법
- 에라토스테네스의 체(이전포스트 참고)
- 테스트개수 for문 안에서{ 2부터 소수 찾기(a) for { a+b == n이 되는 b를 a부터 소수 찾기 for{  } } }
  ( 바쁘면, 맨 밑 코드만 보세요.)

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

int main()
{
	vector<int> num(10001, 0);
	int T;
	cin >> T;

	num[1] = 1;
	for (int i = 2; i*i <= 10000; i++)
	{
		if (num[i] == 0)
			for (int j = i * i; j <= 10000; j += i)
				num[j] = 1;
	}

	for (int k = 0; k < T; k++)
	{
		int n, a, b;
		cin >> n;
		int d = 999999;

		for (int i = 2; i < n; i++)
		{
			if(num[i]==0)
				for (int j = i; j <= n; j++)
					if (num[j] == 0)
						if (n == i + j && j - i < d)
						{
							d = j - i;
							a = i;
							b = j;
						}
		}
		cout << a << " " << b << "\n";
	}

	return 0;
}

 

* 생각하지 못한 점
- 위 코드는 중첩 for문이 3개나 있으므로 당연히 시간초과!!

 

* 수정한 방법
- a가 정해지면 b = n - a임을 이용하면 for문을 한 개 줄일 수 있음
  테스트 개수 for
  {
      소수 구하기 for
      {
          if ( a만 소수이면 되는 것이 아니므로 b도 소수인지 확인 )
             if( a <= b 이고 b - a가 최소인 쌍)
      } 
  }

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

int main()
{
	vector<int> num(10001, 0);
	int T;
	cin >> T;

	num[1] = 1;
	for (int i = 2; i*i <= 10000; i++)
	{
		if (num[i] == 0)
			for (int j = i * i; j <= 10000; j += i)
				num[j] = 1;
	}

	for (int k = 0; k < T; k++)
	{
		int n, a, b;
		cin >> n;
		int d = 999999;

		for (int i = 2; i < n; i++)
		{
			if (num[i] == 0 && num[n - i] == 0)
			{
				if (i <= n - i && n - 2 * i < d)
				{
					a = i;
					b = n - i;
					d = n - 2 * i;
				}
			}
		}
		cout << a << " " << b << "\n";
	}

	return 0;
}