# UVA Problem 543 – Goldbach’s Conjecture Solution

UVA Problem 543 – Goldbach’s Conjecture Solution:

Solving Technique:

First thing to notice is that value of n is always even and range to 1000000. Using naive approach will take a lot of time to check a if number is prime for each iteration.

We can cut down the time using Sieve of Eratosthenes to pre caculate prime numbers from 0 to 1000000 and store them in look up table. So each time we need to check if a number is prime just go to that index a see it the value stored is 1.

The problem statement specifically to find two prime numbers whose sum is equal to n and the difference of these two prime numbers be maximized.

As the conjecture states any even number greater than 4 is sum of two primes. But here the input start from 6 and specifically states that the sum have to be of two odd primes. Since 2 is an even prime it can’t be used.

Now there are multiple odd primes that may add up to n but since the difference between these primes need to be maximized we will always start with the smallest prime number.

For example,

$n = a + b \\ \\ for, n = 42, \\ \\ 42 = 5 + 37 \\ 42 = 11 + 31 \\ 42 = 13 + 29 \\ 42 = 19 + 23 \\ 42 = 23 + 19 \\ 42 = 29 + 13 \\ 42 = 31 + 11 \\ 42 = 37 + 5 \\ \\ \text{From above,} \\ b - a, \\ \\ 37 - 5 > 31 - 11 > 29 - 13 > 23 - 19 > 19 - 23 > 13 - 29 > 11 - 31 > 5 - 37 \\ \\ \text{when,} \\ a = a_{min} \\ b = b_{max} \\ \\ \text{then,} \\ \text{b - a is maximized} \\ \\ \text{So,} \\ n = a_{min} + b_{max} \\ b_{max} = n - a_{min} \\$


Since, we know n, now try prime numbers from 3 to $\frac{n}{2}$ as a and $b = n - a$, when a is prime.
If, b is also a prime then we got our answer and no longer need to calculate. Now print the answer.

Odd prime that make up 42 are,

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

Input:

8
20
42
0


Output:

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37


### Code:

/**
* Author:     Quickgrid ( Asif Ahmed )
* Site:       https://quickgrid.wordpress.com
* Problem:    UVA 543 - Goldbach's Conjecture
* Techniques: Primality Test, Prime Number Generation.
*/

#include<stdio.h>
#include<math.h>

#define N 1000000

/**
* Since value can be up to 1000000
*/
int primesTable[N];

void SieveOfEratosthenes(){

int i = 2;

/**
* Set Every index in the table to be prime.
*/
for(; i <= N; ++i)
primesTable[i] = 1;

/**
* Base case 0 and 1 are not primes.
*/
primesTable[0] = primesTable[1] = 0;

int len = sqrt(N);

/**
* Set all multiples of a number to 0 since primes can't divisible by other than itself.
*/
for(i = 2; i <= len; ++i){
if(primesTable[i]){
for( int k = i * i; k <= N; k += i )
primesTable[k] = 0;
}
}

/**
* 2 is an Even Prime but the question states only odd primes,
* So 2 should be left out.
*/
primesTable[2] = 0;

}

int main() {

SieveOfEratosthenes();

int n;

/**
* Input the number and check if its 0.
*/
while(scanf("%d", &n) && n){

/**
* The bound here does not matter much. a < ( n >> 1 ) will also work.
* But no need for that, max(n) = b - a will be always found before n / 2 for this problem.
*
* Since we are maximizing and starting with the lowest value and
* generating the larger value from that so a and b will be at most n / 2.
*
* If, a + b = n, then if a > n / 2 then, b < n / 2 otherwise a + b != n.
*
* Also start from 3 since 2 is an even prime and not allowed in this problem.
*/
for(int a = 3; a < n; ++a){

if( primesTable[a] ){

/**
* Since, n = a + b
* Them,  b = n - a
*/
int b = n - a;

/**
* Check if the resulting number is prime since a and b both are primes.
* A number may be made up of multiple primes but print the first one since
* we are asked to maximize b - a.
*/
if( primesTable[b] ){
printf("%d = %d + %d\n", n, a, b);
break;
}

}
}

}

return 0;
}