/*  Compile with gcc -o primes primes.c -O3 -lgmp
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <gmp.h>


int main(void)
{
	unsigned long long p_index, p_max = 1;
	
	mpz_t p, p_sqrt;
	mpz_t *primes = malloc (sizeof(mpz_t) * p_max);
	
	mpz_init (p);
	mpz_init (p_sqrt);
	mpz_init (primes[0]);
	
	mpz_set_ui (p, 3);
	mpz_set_ui (primes[0], 3);
	
	for(;;)
	{
		next_p:
		mpz_sqrt (p_sqrt, p);
		mpz_add_ui (p_sqrt, p_sqrt, 1); /* perhaps unnecessary */

		for (p_index = 0; p_index < p_max; p_index++)
		{
			/* a number's factor will never be larger than its square root */
			if ( mpz_cmp (primes[p_index], p_sqrt) > 0 )
				break;

			if ( mpz_divisible_p (p, primes[p_index]) )
			{
				/* the number p is not prime */
				
				/* increment p by 2 */
				mpz_add_ui (p, p, 2);
				
				/* jump! */
				goto next_p;
			}	
		}
		
		/* if we got here that means p was not divisible by any 
		 * of the primes we have in our list which means p must
		 * be prime as well. Add it to the list */
		
		primes = realloc(primes, sizeof(mpz_t) * ++p_max);
		mpz_init (primes[p_max-1]);
		mpz_set (primes[p_max-1],p);
		mpz_add_ui (p, p, 2);
		
		/* show the number */
		mpz_out_str (stdout, 10, primes[p_max-1]);
		putchar (10);
	}
}