[BOJ] 26162 인공 원소 C++

개요

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

26162번: 인공 원소

실버급 소수판정&브루트포스 문제다.

풀이

에라토스테네스의 체로 소수를 판별한 후, 브루트포스로 답을 구했다.

근데 풀고나니까 골드바흐의 추측이란걸 이용하면 훨씬 더 간단히 구할 수 있다는 사실을 알아 버렸다,,

 

골드바흐의 추측

2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것

코드

#include<iostream>
using namespace std;
constexpr int LIMIT = 120;

int N;
int a[LIMIT];
int prime[LIMIT];
string ans[LIMIT];

void solve(int i)
{
	for (int j = 2; j < LIMIT; j++)
	{
		for (int k = 2; k < LIMIT; k++)
		{
			if (j + k != a[i]) continue;
			if (!prime[j] && !prime[k])
			{
				ans[i] = "Yes";
				return;
			}
		}
	}
	ans[i] = "No";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);


	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> a[i];

	for (int i = 2; i < LIMIT; i++)
	{
		int j = i;
		while (i*j<LIMIT)
		{
			prime[i * j] = 1;
			j++;
		}
	}

	for (int i = 0; i < N; i++)
		solve(i);

	for (int i = 0; i < N; i++)
		cout << ans[i] << "\n";
}