/* This is a program to find golbach series :

The algorithm:

Let p a prime, and q the greatest prime less than p

We know G(q) i.e, all even numbers such that cannot be written in the form

x + y, where x and y are primes less or equal than q.

These even numbers will be a part of test vector miss[].

1) We add all even numbers greater than 2*p and less or equal than 2*p to

the test vector.

2) for every number of test vector, say miss[k], we test whether miss[k]-p

is prime. If it is prime, let miss[k]=0

3) Renormalize the test vector, seting all nonzero numbers at the begining

of test vector. The number of nonzero elements is number of laps in G(p).

If all elements in miss[] are zeroes then !we have obtained a full

sequence!

The program uses this recurrent algorithm begining with q=3.

*/

#include <math.h>

#include <iostream.h>

#include <stdio.h>

#include <stdlib.h>

#define nprimos 8192

#define nmiss 8192

unsigned long p[nprimos];

unsigned int miss[nmiss];

unsigned long is_prime(unsigned long l)

{

unsigned long lf=(unsigned long)sqrt(l),j=1;

while ((p[j]<=lf) && (l%p[j]!=0)) j++;

if(p[j]>lf)return 1;

else return 0;

}

int main(void)

{

unsigned long first,last,itest,i,il,imiss,j,jl,lf,jj,aux;

//to prepare function is_prime

//first primes

for(i=0;i<nmiss;i++) miss[i]=0;

p[0]=1;

p[1]=2;

p[2]=3;

p[3]=5;

i=3;

itest=7;

do

{

j=1;

lf=(unsigned long)sqrt(itest);

while ((p[j]<=lf) && (itest%p[j]!=0)) j++;

if(p[j]>lf)

{

i++;

p[i]=itest;

//cout<<"\n"<<i<<" : "<<itest;

}

itest+=2;

}while (i<(nprimos-1));

//hala:;

do

{

cout <<"\nGive me first prime sequence :";

cin >>first;

}while(is_prime(first)==0);

do

{

cout <<"\nGive me last prime sequence :";

cin >>last;

}while( (last<(first+2)));

cout<<"\nAnalizing G("<<first<<").";

il=4; imiss=0;

for(i=3;i<=first;i+=2)

{

if(is_prime(i))

{

jl=2*i;

for(j=il+2;j<=jl;j+=2)

{

miss[imiss++]=j;

}

for(j=0;j<imiss;j++)

{

if(is_prime(miss[j]-i)) miss[j]=0;

}

il=jl;

jj=0;

for(j=0;j<imiss;j++)

{

if(miss[j]!=0)

{

aux=miss[j];

miss[j]=0;

miss[jj++]=aux;

}

}

imiss=jj;

}

}

for(i=first+2;i<=last;i+=2)

{

if(is_prime(i))

{

jl=2*i;

for(j=il+2;j<=jl;j+=2)

{

miss[imiss++]=j;

}

for(j=0;j<imiss;j++)

{

if(is_prime(miss[j]-i)) miss[j]=0;

}

il=jl;

jj=0;

for(j=0;j<imiss;j++)

{

if(miss[j]!=0)

{

aux=miss[j];

miss[j]=0;

miss[jj++]=aux;

}

}

imiss=jj;

if(imiss == 0) cout<<"\nG("<<i<<") has 0 laps !full sequence!";

else

{

if(miss[0]<=(3+i))

{

cout<<"\n !!! Goldbach's Conjecture is false !!! :\n";

cout<< miss[0] <<" cannot be written like sum of two primes";

break;

}

cout<<"\nG("<<i<<") is incomplete, has "<<imiss<<" laps.";

}

}

}

//goto hala;

return 0;

}