UVA online judge 543
Goldbach's conjecture
Link:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=484
Solution:
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
int primes[N];
void Sieve()
{
int i;
for(i=2; i<=N; i++)
primes[i] = 1;
primes[0] = primes[1] = 0;
int len = sqrt(N);
for(i = 2; i <= len; ++i)
{
if(primes[i])
{
for( int k = i * i; k <= N; k += i )
primes[k] = 0;
}
}
primes[2] = 0;
}
int main()
{
Sieve();
int n,b,a;
while(scanf("%d", &n)&&n)
{
for( a = 3; a < n; ++a)
{
if( primes[a] )
{
b = n - a;
if( primes[b] )
{
// printf("%d = %d + %d\n", n, a, b);
cout <<n<<" "<<"="<<" "<<a<<" "<<"+"<<" "<<b<<endl;
break;
}
}
}
if(a+b!=n)
// printf("Goldbach's conjecture is wrong\n");
cout <<"Goldbach's conjecture is wrong"<< endl;
}
return 0;
}