//EKG.cpp
//solves EKG problem FAST

/*
solving this problem using straightforward computations is very inefficient
the method used computes the smallest prime factor of each integer
and the corresponding coprime factor. This allows you to work your way
back through the numbers efficiently to finding the smallest unused non-coprime
integer
*/

#include <iostream>
using namespace std;
#include <math.h>

// ************ global variables ****************
const long int MAX=1000000;   //the largest position in the EKG sequence that we'll find
long int EKG[MAX],            //EKG[i] = position in seq. of i
         A[MAX],              //A[i] = smallest prime divisor of i
         factor[MAX],         //factor[i] = largest factor of i coprime to A[i]
         small[MAX];          //small[i] = smallest unused multiple of i - used in NextOne()

/*******************************************************************
  compute the next elt in the EKG seq (next) given the last one (last)
*/
void NextOne(long int &last, long int & next) {
  long int a,b, smallest;

  a = A[last];
  b = factor[last];
  smallest=small[a];
  // find smallest multiple of all prime factors of i not used
  while(b>1){
    a=A[b];
    b=factor[b];
    if(smallest>small[a]) smallest=small[a];
  }
  next=smallest;            //that's the next number in the sequence
 
  //update smallest for all i st small[i]==smallest
  b=smallest;
  a=A[b];
  while(a>1){
    if(small[a]==smallest){
      small[a]+=a;
      while(small[a]<MAX && EKG[small[a]]) small[a]+=a;
    }
    b=factor[b];
    a=A[b];
  }
}

//*******************************************************************
int main(){
  long int n;
  long int i,  j, last, next;

  for(i=1;i<MAX;i++) A[i]=i;
  //use Sieve to find smallest prime divisors
  for(i=2;i<sqrt((double)MAX);i++)
    if(A[i]==i){ //i prime
      j = i+i;
      while(j<MAX){
        if(A[j]==j) A[j]=i;
        j += i;
      }
    }

  //find largest factor of i coprime with A[i]
  for(i=2;i<MAX;i++){
    factor[i] = i/A[i];
    while(factor[i]%A[i]==0) factor[i] /= A[i];
  }

  //initalize EKG[]
  EKG[1]=1; EKG[2]=2;
  for(i=3;i<MAX;i++)
    EKG[i]=0;

  // init smallest unused multiple list
  for(i=3;i<MAX;i++) small[i]=i;
  small[2]=4;

  //EKG[i]= position of i  in EKG sequence
  //now fill in the rest of EKG[]
  last=2;
  i=3;     
  //finding the ith EKG number
  NextOne(last,next);
  while(next<MAX) {      //only compute until you get a number too large
    EKG[next]=i;
    last = next;
    i++;
    NextOne(last,next);
  }
 
/*       for debugging to see what the longest continuous run is
            (333340 for MAX = 1000000)

cout<<"finished with EKG[]"<<endl;
//find last EKG number
i=1;
while(EKG[i]) i++;
cout<<"Last EKG number is "<<i-1<<endl;
*/

  cin>>n;
  while(n>0) {
    cout<<"The number "<<n<<" appears in location "<<EKG[n]<<"."<<endl; 
    cin>>n;
  }
 return 0;
}
