/*
 * Prime Number Generator, by Tobin Creek
 *
 * Algorithm: keep a linked-list of prime numbers in memory, starting with
 * 2.  Start with a dividend of 2.  Test all prime numbers less than
 * the square root of the number being tested. 	Since any factor can be 
 * broken down to prime numbers, we need not test all numbers as possible
 * factors, just prime ones.  Since factors repeat after the square root,
 * we need not test any factors above this point.  Any numbers with prime
 * integer square roots are not prime, so we must test the factor equal
 * to the square root.  Store the prime and it's square, so that we need
 * not calculate the square every time to see how far we need to test.
 * A common trade of memory for speed.
 *
 * Signal handling has been added, to allow interruption of the program
 * and printing of the number of primes found and the run time taken
 * to find them upon reciept of the signal.  Also given on exit.
 *
 * Compile instructions: cc -fast -o prime prime.c
 *
 * This algorithm may not be the fastest, but it is mine, Mine, MINE
 * and was developed without peeking at anyone else's code or ideas.
 */

#include <stdio.h>
#include <math.h>
#include <values.h>
#include <signal.h>
#include <sys/resource.h>

/* Global, so that we can spew it out when a signal is handled. */
int numprimes = 0;

/* Define the linked list structure for the list of primes. */
struct primelist {
	unsigned long int primenumber;
	unsigned long int primesquare;
	struct primelist *nextprime;
};

/* Report resource usage */
void timetaken(void)
{
	struct rusage r_usage;

	getrusage(RUSAGE_SELF, &r_usage);
	printf("Found %d prime numbers in %ld seconds.\n", numprimes,
		r_usage.ru_utime.tv_sec + r_usage.ru_stime.tv_sec);
	fflush(stdout);
}

/* The signal handler - called on HUP, INT, or TERM. */
void signal_handler(int sig)
{
	fprintf(stderr, "\nSignal Caught!  Exiting...\n");
	timetaken();
	exit(1);
}

main(int argc, char *argv[])
{
	unsigned long int divisor, dividend, lastdividend;
	unsigned long sqrcurrent, sqrtld, nextprime;
	short int prime;
	struct primelist *head = NULL, *current, *tail;
	FILE *primefile;
	char primeline[30];

	/* Setup the signals.  Always in effect. */
	signal(SIGHUP, signal_handler);
	signal(SIGINT, signal_handler);
	signal(SIGQUIT, signal_handler);
	signal(SIGTERM, signal_handler);

	/* Allow the user to specify a stopping point on the command line. 
	 * Otherwise, use 2^31 - 1). */
	if ( argc >= 2 ) {
		lastdividend = atol(argv[1]);
		printf("INFO: Stopping at %ld\n",lastdividend);
	} else
		lastdividend = 4294967295;

	sqrtld = (unsigned long)sqrt((double)lastdividend);

	/* Attempt to open a list of primes from a previous run */
	primefile = fopen("primelist.txt", "r");

	/* If file does not exist, print an error, initialize the linked-list
	 * with a single prime number (2), and start the testing at 2. 
	 * If file does exist, load the primes up to the square-root of the
	 * stopping point. Set the starting point to the last prime in the
	 * file + 1 (the dividend increments at the beginning of the loop). */
	if ( ! primefile ) {
		printf("INFO: Unable to load primelist.txt.\n");
		head = (struct primelist *)malloc(sizeof(struct primelist));
		head->primenumber = 2;
		/* We'll always test 2, so why bother with it's prime? */
		head->primesquare = 0;
		head->nextprime = NULL;
		dividend = 1;
		tail = head;
	} else {
		head = (struct primelist *)malloc(sizeof(struct primelist));
		head->nextprime = NULL;
		tail = head;
		current = head;
		while ( fgets(primeline, 30, primefile) != NULL) {
			nextprime = atol(primeline);
			if ( nextprime <= sqrtld ) {
				if ( !current ) {
					current =
						(struct primelist *)malloc(sizeof(struct primelist));
					current->nextprime = NULL;
				}
				current->primenumber = nextprime;
				/* Since we will resume at the last prime + 1, we only load
				 * the primes that we need to reach the endpoint.  We will
				 * always test these, since they are less than the square root
				 * of the endpoint (since we test this condition on load). */
				current->primesquare = 0;
				tail->nextprime = current;
				tail = current;
				current = NULL;
			}
		}
		/* If we knew this number in advance, we could shorten the load time,
		 * but currently, I don't want to implement this. */
		dividend = atol(primeline);
		fclose(primefile);
		printf("INFO: Resuming at %ld\n", dividend);
	}
		
	/* Open this list of primes and begin appending.  */
	primefile = fopen("primelist.txt", "a");

	/* Disable I/O buffering, to make the progress easier to watch. */
	setbuf(primefile, (char *)NULL);
	while ( dividend <= lastdividend ) {
		dividend++;
		current = head;
		prime = 1;
		/* Traverse the list of primes until exhausted, or until we reach
		 * a prime that exceeds the square-root of the dividend.  */
		while ( current && ( current->primesquare <= dividend ) ) {
			divisor = current->primenumber;
			if ( (dividend % divisor) == 0 ) {
				prime = 0;
				break;
			}
			current = current->nextprime;
		}
		/* If prime, print to the file. */
		if ( prime || dividend == 2 ) {
			fprintf(primefile,"%ld\n",dividend);
			numprimes++;
			/* If the largest prime < the square-root of the last dividend,
			 * add to the list. */
			if ( dividend < sqrtld ) {
				current = (struct primelist *)malloc(sizeof(struct primelist));
				current->primenumber = dividend;
				current->primesquare = dividend * dividend;
				current->nextprime = NULL;
				tail->nextprime = current;
				tail = current;
			}
		}
	}

	/* Print the last prime in the in-memory table, for informational
	 * purposes. */
	printf("INFO: Last prime stored was %ld.\n", tail->primenumber);

	/* Close the prime file. */
	fclose(primefile);

	/* Print run time. */
	timetaken();

	exit(0);
}