UVa 10948 - The primary problem

// UVa 10948 - The primary problem

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

bool isprime[1000001];
vector<int> prime;

int main() {
	// sieve
	memset(isprime, true, sizeof(isprime));
	for (int i = 4; i <= 1000000; i += 2)
		isprime[i] = false;
	prime.push_back(2);
	for (int i = 3; i <= 1000; i += 2)
		if (isprime[i]) {
			prime.push_back(i);
			for (int j = i * i; j <= 1000000; j += (i << 1))
				isprime[j] = false;
		}
	for (int i = 1001; i < 1000000; i += 2)
		if (isprime[i])
			prime.push_back(i);

	while (true) {
		// input
		int n;
		scanf("%d", &n);
		if (n == 0)
			break;
		printf("%d:\n", n);
		bool found = false;
		for (int i = 0; i < prime.size() && (prime[i] << 1) <= n; i++)
			if (isprime[n - prime[i]]) {
				printf("%d+%d\n", prime[i], n - prime[i]);
				found = true;
				break;
			}
		if (!found)
			printf("NO WAY!\n");

		// output
	}
	return 0;
}