#include <stdio.h>
#include <stdlib.h>
#include "../../primes/primetab.cc"

typedef long long  ptype;
typedef long long pptype; // primepowers

static const int blocksize=250000;
static ptype phi[blocksize];
static ptype val[blocksize];
static const int nump=10000;

ptype gcd(ptype h, ptype l)
{
    while(l) { h%=l; if(!h)return l; l%=h; } return h;
}
int main(int i, char**argv)
{
    ptype min=00000000ll;
    int interesting=0;
    while(min<600000000ll)
    {
	const ptype proxymin=min+!min;
	const int proxysize=blocksize-!min;
	fprintf(stderr, "BLOCK: %lli + %i\n", proxymin, proxysize);
        fflush(NULL);
	for(int i=0; i<proxysize; ++i)
	{
	    phi[i]=val[i]=1;
	}
	
	for(int pi=0; pi<nump; ++pi)
	{
	    int p=primetable[pi];
	    if((pptype)p*p>proxymin+proxysize) break; // only trial divide to half way
	    ptype phicontrib=p-1;
	    pptype pp=1;
	    pptype index;
	    do
	    {
		pp*=p;
		index=pp-1; // as far into the array as we could ever start
		index-=(proxymin+index)%pp; // now index>=0 in array, do this one
		//if(0 && index<proxysize) 
		//    printf("Prime %u power %lli: starts at %lli=%lli\n", p, pp, index, proxymin+index);
		while(index<proxysize)
		{
		    phi[index]*=phicontrib;
		    val[index]*=p;
		    //if(0)
		    //printf("[%lli] has %lli -> %lli ; %lli (%lli left)\n",
		    //   index+proxymin, pp, val[index], phi[index], 
		    //   (index+proxymin)/val[index]);
		    index+=pp;
		}
		phicontrib=p;
	    } while(index>=pp);
	}

	for(int i=0; i<proxysize; ++i)
	{
	    ptype p=proxymin+i, ph=phi[i];
	    //printf("p=%i phi=%i\n", p, ph);
	    if(ph==1||ph==p-1) continue; // don't do primes
	    
	    if(val[i]<(p>>1))
	    {
		// must factorise
		// printf("%u has prime %u left\n", (proxymin+i), (proxymin+i)/val[i]);
	        ph *= (p/val[i]-1);
	    }
	    // want p-1 (thanks Erick!)
	    --p;

	    ptype g=gcd(p, ph);
	    if(ph<100*g)
	    {
		++interesting;
		printf("%i) p=%lli phi=%lli (gcd=%lli) ratio=%lli/%lli\n", 
		       interesting, p+1, ph, g, p/g, ph/g);
	    }
	}
	min+=blocksize;
    }
}