/* written by John Moyer, copyright 2009 */
/* inefficient way to print prime numbers with some duplication and unsorted */
/* 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/ */
/* output should be piped to sort -n | uniq */
/* compiled under windows with mingw32 command line:
	gcc -Wall -O3 -o find_primes.exe find_primes.c
*/
/* mailto:jrm@rsok.com */
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <inttypes.h>

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;


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;

for ( r = 3; r < ii; r++ )
  {
  j = gcd(r, q);
  i = q + j;
  jj = i - q;
  if ( (jj) != 1 )
    {
    printf("%"PRIu64"\n", jj );
    }
  q = i;
  }

return 0;
}