#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char* make_prime_table(long n)
{
    char* tab;
    long i, j, limits;

    if((tab = (char *)malloc((n + 1) * sizeof(int))) == NULL)
    {
	perror("malloc");
	exit(1);
    }
    memset(tab, 0, (n + 1) * sizeof(int));

    tab[0] = 1;
    tab[1] = 1;
    limits = (int)(sqrt((double)n) + 1);

    for(i = 2; i <= limits; i++)
    {
	if(tab[i]) 
	    continue;
	for(j = i * 2; j <= n; j += i)
	    tab[j] = 1;
    }

    return tab;
}

#define PRIME_BLOCK_SIZE 65536
struct prime_block
{
    long size;
    long* prime;
    struct prime_block* next;
};

struct prime_block* new_prime_block(void)
{
    struct prime_block* p;

    if((p = (struct prime_block *)malloc(sizeof(struct prime_block))) == NULL)
    {
	perror("malloc");
	exit(1);
    }
    if((p->prime = (long *)malloc(PRIME_BLOCK_SIZE * sizeof(long))) == NULL)
    {
	perror("malloc");
	exit(1);
    }

    p->size = 0;
    p->next = NULL;

    return p;
}

void all_prime(void)
{
    struct prime_block *first, *last;
    char* tab;
    long prime_test, i, j;

    prime_test = 100;
    first = last = new_prime_block();
    tab = make_prime_table(prime_test);
    for(j = i = 0; i < prime_test; i++)
	if(!tab[i])
	    first->prime[j++] = i;
    first->size = j;
    for(i = 0; i < j; i++)
	printf("%ld ", first->prime[i]);
    fflush(stdout);

    while(1)
    {
	struct prime_block* cur;

	for(cur = first; cur; cur = cur->next)
	{
	    long n, *p, t;

	    n = cur->size;
	    p = cur->prime;
	    t = prime_test;

	    for(i = 0; i < n; i++)
		if(t % p[i] == 0)
		    goto next_test;
	}

	printf("%ld ", prime_test);
	fflush(stdout);
	if(last->size == PRIME_BLOCK_SIZE)
	    last = last->next = new_prime_block();
	last->prime[last->size++] = prime_test;

      next_test:
	prime_test++;
    }
}

int main(int argc, char** argv)
{
    if(argc == 1)
    {
	all_prime();
    }
    else
    {
	long i, n;
	char* tab;

	n = atoi(argv[1]);
	tab = make_prime_table(n);
	for(i = 0; i <= n; i++)
	    if(!tab[i])
		printf("%ld ", i);
	printf("\n");
    }
    return 0;
}