UVA Problem 543 – Goldbach’s Conjecture Solution

UVA Problem 543 – Goldbach’s Conjecture Solution:


Click here to go to this problem in uva Online Judge.

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,

UVA 543 Goldbachs Conjecture Diagram
UVA 543 Goldbachs Conjecture Diagram

 

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;
}
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s