#include <stdio.h> #include <stdlib.h> int sieve (int *x, int *y, int b, int n, int nx) { int i; int ny = 1; #if 0 printf ("sieving %d mod %d\n", b, n); printf (" before:"); for (i=1; i<nx; i++) printf (" %d", x[i]); printf ("\n"); #endif for (i=1; i<nx; i++) { if (i != b && i%n == b%n) continue; y[ny++] = x[i]; } for (i=1; i<ny; i++) { x[i] = y[i]; } #if 0 printf (" after:"); for (i=1; i<ny; i++) printf (" %d", x[i]); printf ("\n"); #endif return ny; } int main (int ac, char **av) { int i; int N = 1000000; int *x; int *y; int nx; if (ac > 1) N = atoi(av[1]); x = (int *) malloc (N * sizeof (int)); y = (int *) malloc (N * sizeof (int)); for (i=1; i<N; i++) { x[i] = i; } nx = N; for (i=2; i < nx && i + x[i]<nx; i++) { nx = sieve (x, y, i, x[i], nx); } for (i=1; i<nx; i++) printf ("%d\n", x[i]); return 0; }