UVA 686 - Goldbach's Conjecture (II)(c++ file)

Problem Type : Number Theory


#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
bool arr[5000000];
vector <long int> prime;
void sieve(long int N)
{
    long  int k = sqrt(N);
    for(long int i=3; i<=k; i+=2)
    {
        if(arr[i]==0)
        {
            for(long int j=i*i; j<=N; j+=2*i)
            {
                arr[j] = 1;
            }
        }
    }
    arr[1] = 1;
    for(long int i=4; i<=N; i+=2)
    {
        arr[i] = 1;
    }

    prime.push_back(2);
    for(long int i=3; i<=N; i+=2)
    {
        if(arr[i]==0)
            prime.push_back(i);
    }
}

int main()
{

    long int n,i,j,count,l,same;
    sieve(100000);
    while(scanf("%ld",&n)==1)
    {
        if(n==0)
            break;
        count=0;
        same =0;
        l=n/2;
        for(i=0; i<l; i++)
        {
            for(j=0; j<n; j++)
            {
                if(prime[i]==prime[j]&& prime[i]+prime[j]==n)
                {
                    same++;
                }
                else if(prime[i]+prime[j]==n)
                {
                    count++;
                }

                if(prime[i]+prime[j]>n)
                    break;
            }
        }
        count = count/2 +same;
        printf("%ld\n",count);
        prime.clear();
    }
    return 0;
}