[백준 6588번] 골드바흐의 추측 (C++)

문제링크 : https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); 
#define ll long long

int arr[1000001];

void makePrime() {
	for(int i=2; i*i<=1000000; i++)
    {
        for(int j= 2*i; j<=1000000; j+=i)  //i값으로 나눠지므로 j+=i
        {
             arr[j]=1;
        }
    }
}

int main() {
	fastio;
	int n;
    makePrime();
	while (1)
	{
		cin >> n;
        if(n==0) break;
        bool check = false;
		for (int i = 3; i <=n; i+=2)  //짝수는 볼 필요가 없으므로 i+=2
		{
			if (arr[i]==0 && arr[n-i]==0)
			{
				cout << n << " = " << i << " + " << n-i << "\n";
				check = true;
				break;
			}
		}
		if (!check) { cout << "Goldbach's conjecture is wrong\n"; }
	}
}

처음에 각 값에 대해 일일이 소수인지 아닌지 판별하는 방식으로 풀었다가 시간초과가 굉장히 많이 났던 문제다.

미리 범위값만큼 소수인지 아닌지 에라스토테네스의 체 방식으로 구해놓고 시작해야 한다.