백준 9020번 - 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

사고과정)

우선 해당 수보다 작은 소수들을 찾으려했다.

짝수들은 소수가 아니기 때문에 반복문 조건에서 +2로 해주었다.

 2와 3은 예외처리를 해주었다.

그 이후 이중반복문으로 소수 배열의 원소 두개를 더하고 input값이랑 같으면

그 차이를 가장 작게 한걸 pair로 저장하게 했다.

#include <iostream>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;
int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;
		vector<int> primes;
		pair<int, int> result;
		// 짝수는 기본적으로 소수가 아니다. 2를 제외하곤.
		primes.push_back(2); // 예외처리
		for (int k = 3; k < input; k += 2)
		{
			if (k == 3)
			{
				primes.push_back(k);
				continue;
			}
			int sqr = (int)sqrt(k);
			for (int j = 2; j <= sqr; j++)
			{
				if (k % j == 0)
					break;
				if (j == sqr)
					primes.push_back(k);
			}
		}
		int dif = 10000;
		for (int j = 0; j < primes.size(); j++)
		{
			for (int k = j; k < primes.size(); k++)
			{
				int sum = primes[k] + primes[j];
				if (sum == input)
				{
					int temp = (primes[k] - primes[j]);
					if (temp < dif)
					{
						dif = temp;
						result = make_pair(primes[j], primes[k]);
					}
				}
			}
		}
		cout << result.first << ' ' << result.second << '\n';
	}
}

굳이 반복문 두개가 다 size()만큼 돌릴 필요가 없을 듯 싶어 수정해봤다.

		bool flag = false;
		for (int j = 0; j < primes.size(); j++)
		{
			for (int k = 0; k <= j; k++)
			{
				int sum = primes[k] + primes[j];
				if (sum == input)
				{
					cout << primes[k] << ' ' << primes[j] << '\n';
					flag = true;
					break;
				}
			}
			if (flag)
				break;
		}

꽤 줄었다.