백준 6588번 골드바흐의 추측

에라토스테네스의 체 복습하는 기회가 되었다!

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <iostream>
using namespace std;

int main() {
	int arr[1000005] = {};
	int prime[1000004];
	arr[1] = 1;
	for (int i = 2; i <= 1000000;i++) {
		for (int j = 2; i*j <= 1000000;j++) {
			arr[i*j] = 1;
		}
	}
	
	int n=-1;
	while (1) {
		scanf("%d", &n);
		if (n == 0)
			break;
		for (int i = 3; i <= n - 1; i++) {
			if (!arr[i]) {
				int j = n - i;
				if (!arr[j]) {
					printf("%d = %d + %d\n", n, i, j);
					break;
				}
			}
		}
			
	}
}