/* primes.c
 * Written 14 Jan 2007 by John T. Wodder II <jwodder@sdf.lonestar.org>
 * Last edited 16 Feb 2008 by John Wodder
 */

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

/* #define TIMED */
#ifdef TIMED
#include <sys/time.h>
#endif

int main(int argc, char** argv) {
 int qty = (argc > 1) ? atoi(argv[1]) : 100;
 if (qty < 3) qty = 100;
 unsigned long* primes = calloc(qty, sizeof(unsigned long));
 if (primes == NULL) {perror("primes"); return 1; }
 primes[0] = 2; primes[1] = 3;
 printf("2\n3\n");
#ifdef TIMED
 struct timeval start, end;
 gettimeofday(&start, NULL);
#endif
 for (int i=2; i<qty; i++) {
  int j = primes[i-1];
  iter: j += 2;
  unsigned long bound = lround(sqrt(j));
  for (int k=1; k<i; k++) {
   if (primes[k] > bound) break; /*Not a viable shortcut for small quantities*/
   if (!(j % primes[k])) goto iter;
  }
  primes[i] = j;
  printf("%lu\n", j);
 }
#ifdef TIMED
 gettimeofday(&end, NULL);
 printf("Time spent: %ld:%06ld\n", end.tv_sec - start.tv_sec, end.tv_usec -
  start.tv_usec);
#endif
 return 0;
}