/* primes.c
* Written 14 Jan 2007 by John T. Wodder II <
[email protected]>
* 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;
}
