Wednesday, June 10, 2015

UVa 543 - Goldbach's Conjecture

// UVa 543 - Goldbach's Conjecture

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

#define integer unsigned long long

int main() {
	// initialize
	vector<integer> primes;
	bool prime[1000001];
	memset(prime, true, sizeof(prime));
	prime[1] = false;
	// consider number 2
	primes.push_back(2);
	for (integer i = 4; i <= 1000000; i += 2)
		prime[i] = false;
	// sieve
	for (integer i = 3; i <= 1000000; i += 2)
		if (prime[i]) {
			primes.push_back(i);
			for (integer j = i * i; j <= 1000000; j += (i << 1))
				prime[j] = false;
		}
	// prob
	integer n;
	while ((cin >> n) && n) {
		for (integer i = 0; i < primes.size(); i++) {
			if (prime[n - primes[i]]) {
				printf("%llu = %llu + %llu\n", n, primes[i], n - primes[i]);
				break;
			}
		}
	}
	return 0;
}

No comments:

Post a Comment