Be a programmer,be logical : Goldbach's Conjecture(Number theory)

Be a programmer,be logical : Goldbach's Conjecture(Number theory):

Goldbach's Conjecture(Number theory)

Now i am going to discuss about an important theory of number theory that is Goldbach's conjecture.Hope u will enjoy:

For any integer n (n ≥ 4) there exist two prime numbers p₁ and p₂ such that p₁ + p₂ = n. In a problem we might need to find the number of essentially different pairs (p₁, p₂), satisfying the condition in the conjecture for a given even number n (4 ≤ n ≤ 2¹⁵). (The word ‘essentially’ means that for each pair (p₁, p₂) we have p₁ ≤ p₂.)For example, for n = 10 we have two such pairs: 10 = 5 + 5 and 10 = 3 + 7.

To solve this,as n ≤ 2¹⁵ = 32768, we’ll fill an array primes[32768] using function seive. We are interested in primes, not greater than 32768.

The function FindSol(n) finds the number of different pairs (p₁, p₂), for which n = p₁ + p₂. As p₁ ≤ p₂, we have p₁ ≤ n/2. So to solve the problem we need to find the number of pairs (i, n – i), such that i and n – i are prime numbers and 2 ≤ i ≤ n/2.

int FindSol(int n)

{

       int i, res=0;

       for(i=2;i<=n/2;i++)

              if(flag[i] && flag[n-i])

                    res++;

       return res;  

}

******another effective******

For this all the primes should be generated first

int FindSol(int n)

{

    int i, res=0;

//here prime[i] is a prime if (n-prime[i]) be prime then whole pair will be prime;

    for(i=0; prime[i]<=n/2; i++)       {

        if(table[n-prime[i]]==false) res++;

    }

    return res;



By the help of this theory,i hope u all will solve the following problems
1.http://www.lightoj.com/volume_showproblem.php?problem=1259 
2.https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=627