// 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; }
Wednesday, June 10, 2015
UVa 543 - Goldbach's Conjecture
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment