/* written by John Moyer, copyright 2009 */
/* inefficient way to print prime numbers sorted and unique */
/* from E. S. Rowland A natural prime-generating recurrence J.Integer Seq.,
 v.11(2008), Article 08.2.8 */
/* http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.pdf */
/* http://www2.research.att.com/~njas/sequences/A137613 */
/* http://www2.research.att.com/~njas/sequences/A132199 */
/* http://arxiv.org/abs/0710.3217 */
/* http://thenksblog.wordpress.com/2008/07/21/a-simple-recurrence-that-produces-complex-behavior-and-primes/ */
/* compiled under windows with mingw32 command line:
	g++ -Wall -O3 -o find_primes.exe find_primes.cpp
*/
/* mailto:jrm@rsok.com */

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <inttypes.h>
#include <list>
// #include <algorithm>
// #include <iterator>
#include <iostream>

using namespace std;

/* uint64_t may be non-standard in C++since it is from C99, but so far as
   I know, the C++ standard does not specify which version of C is supported.
*/
uint64_t gcd(uint64_t i, uint64_t j)
{
uint64_t r, q;

if ( j < i )
  {
  r = i;
  i = j;
  j = r;
  }	/* swap them */

while ( i != 0 )
  {
  r = j % i;
  q = j / i;
  j = i;
  i = r;
  }
return j;
}


int main(int argc, char *argv[])
{
uint64_t ii, jj, i, j, r, q;
list<uint64_t> li;
list<uint64_t>::iterator it;

if (argc!=2)
  {
  fprintf(stderr, "Usage: %s integer\n", argv[0]);
  return -1;
  }

ii = strtoull(argv[1],NULL,0);

  /* a(1) == 7 */
  /* a(2) == a(1) + gcd(2, a(1) ) = 7 + gcd(2,7) = 8 */
  /* a(3) == a(2) + gcd(3, a(2) ) = 8 + gcd(3,8) = 9 */
q = 8;
i = q;

li.insert(li.begin(), 2);	// first prime

for ( r = 3; r < ii; r++ )
  {
  j = gcd(r, q);
  i = q + j;
  jj = i - q;
  if ( (jj) != 1 )	// if prime
    {
//    cerr << jj << endl; // uncomment if you want to see the unsorted values
    for ( it = li.begin() ; it != li.end() ; it++)
      {
      if ( *it == jj )	// if we have already found this prime, then skip
        break;
      if ( *it > jj )	// if larger then insert before
        {
        li.insert(it,jj);
        break;
        }
      }
    if ( it == li.end() )	// if larger than all previously found
      {
      li.push_back(jj);		// put it at the end of the list
      }
    
    }
  q = i;
  }

 for(it = li.begin(); it != li.end(); it++)
  {
  cout << *it << endl;
  }

return 0;
}