======Project: Prime Number Calculator======

A project for Data Structures by Tyler Galpin during the Fall 2011.

This project took about one day to complete and was completed on December 16th, 2011.

=====Objectives=====
The point of this project is to use linked lists and sorting algorithms to create a list of prime numbers and composite numbers on a given interval.

=====Prerequisites=====
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

  * Working linked list library
  * Understanding of prime numbers
  * Algorithm to test for prime numbers

=====Background=====
As I've stated already, a proper algorithm is needed to determine whether a number is prime. This algorithm should:

  *Start from the lower bound number (2)
  *Reiterate until the current number is greater than the upper bound
  *Send prime numbers to one linked list, composites to another
  *Check for a remainder in the division of the current number by every number from the lower bound to itself (MOD division)

=====Scope=====
This program will compute the prime numbers from 2 to just about any number your computer can handle. Formatting may be an issue with really large numbers, but it will do the job.

=====Attributes=====


  * linked list: The stack is based off of a linked list
  * doubly linked list: The stack uses a doubly linked list.
  * pointers: make up the backbone of the data structure
  * malloc: needed in the creation of new stacks/nodes
  * sorts: Needed to determine which numbers are prime!
  * File I/O: Used to accept upper bound number

=====Code=====

===main.c===
<code c>
/*
 * Prime numbers project
 *                  + EOCE Assignment
 *
 * Fall2011 Data Structures
 *
 * To compile: gcc -o [output file] [source code]
 *
 * Known problems: n/a
 *
 */

// Include files
#include <stdio.h>
#include <stdlib.h>

// Create our node structure to store the prime numbers
struct node {
	int value;
	struct node *next;
	struct node *prev;
};
//Node contains pointers to next and previous nodes,
//and holds an integer value.
typedef struct node Node;// From now on, 'Node' means the same
			 // as 'struct node' in this code

Node *prime, *composite, *ptop, *ctop, *tmp, *tmp2;
			//initialize nodes for prime and composite lists
			//prime/composite (first node), ptop/ctop (last node)

void pushPrime(int); // function to push prime number to list
void pushComposite(int); // push composite numbers to other list
void displayLists(); //Displays all prime/composites

// main function
int main()
{
	int upper, n=2, d=2; //initialize upper bound variable, first and second for-loop values
	puts("\n     [Prime Program]: "); 
	puts("Find all prime numbers from 2 to a given number.\n");
	do
	{
		puts("Enter an upper bound value (greater than two (2)): ");
		scanf("%d", &upper); //Accept integer for upper bound 
		if (upper <= 2)
		{
			puts("\n\n!!ERROR!! : Enter a value greater than two (2).\n\n");
			//print error message if value is not greater than two
		}
	} while (upper <= 2); //execute loop as long as user's input is not greater than two
	for(n=2;n<=upper;n++)
			//Execute loop for as long as n (currently evaluated integer)
			//is between 2 and the given upper bound
	{
		for(d=2; d<=n; d++)
			//Execute loop as long as d (the current denominator)
			//is less than or equal to the current n
		{
			if(n % d == 0 && d != n)
			//Composite test: If the division between n and d leaves
			//no remainder (note the use of the mod operator), and
			// d isn't equal to n, then n is a composite number
			{
				pushComposite(n); //Send n to composite list
				break; //Break operation, loop does not need to continue for this iteration
			}
			else if (d == n) //If n fails the composite test until n=d, it is prime
			{
				pushPrime(n); //Push n to prime list
			}				
		}
	}
	displayLists(); //Display the two lists
	return(0);
}

void pushPrime(int value) //returns no value, accepts value to be added to list
{
	if (prime==NULL) //No values in list, create first node
	{
		prime = (Node *) malloc(sizeof(Node));
		ptop=prime;
		prime->next=NULL;
		prime->prev=NULL;
		tmp=prime;
		prime->value=value;
	}
	else if (prime == ptop) //there is only one node, create a second
	{
		tmp= (Node *) malloc(sizeof(Node));
		ptop->next=tmp;
		tmp->prev=ptop;
		ptop=ptop->next;
		ptop->value=value;
		ptop->next=NULL;
	}
	else //more than one node, add more to list
	{
		tmp=prime;
		int i=0;
	       	while(tmp != NULL)
	        {   
        	        i++;
                	tmp=tmp->next;
       		}   
        	tmp = (Node *) malloc (sizeof(Node));
        	ptop -> next = tmp;
        	tmp -> prev = ptop;
        	ptop = ptop -> next;
        	ptop -> value = value;
        	ptop -> next = NULL;
	}
}

void pushComposite(int value) //return no value, accept value to add to composite list
{
	if (composite==NULL) // no values in list, create first node
	{
		composite = (Node *) malloc(sizeof(Node));
		ctop=composite;
		composite->next=NULL;
		composite->prev=NULL;
		tmp2=composite;
		composite->value=value;
	}
	else if (composite == ctop) // only one node, create second node
	{
		tmp2= (Node *) malloc(sizeof(Node));
		ctop->next=tmp2;
		tmp2->prev=ctop;
		ctop=ctop->next;
		ctop->value=value;
		ctop->next=NULL;
	}
	else //more than one node, add more to end of list
	{
		tmp2=composite;
		int i=0;
	       	while(tmp != NULL)
	        {   
        	        i++;
                	tmp=tmp->next;
       		}   
        	tmp2 = (Node *) malloc (sizeof(Node));
        	ctop -> next = tmp2;
        	tmp2 -> prev = ctop;
        	ctop = ctop -> next;
        	ctop -> value = value;
        	ctop -> next = NULL;
	}
}

void displayLists() // display lists
{
	tmp=prime; // set tmp to first prime value
	puts("\nPrime numbers:");
	while(tmp != NULL) //while not at the end of the list
	{
		printf("[%d] ", tmp->value); //print value
		tmp=tmp->next; //move to next value
	}
	tmp2=composite; //set tmp2 to first composite value
	puts("\nComposite numbers:");
	while(tmp2 != NULL) //while not at end of list
	{
		printf("[%d] ", tmp2->value); // print value
		tmp2=tmp2->next; //move to next node
	}
	puts("\n");
}
</code>

=====Execution=====
This is how to compile and execute:
<cli>
lab46:~/src/data/prime$ gcc -o prime main.c
lab46:~/src/data/prime$ ./prime
</cli>

=====Reflection=====
Making the algorithm was a little difficult at times. I had the general idea of the algorithm down from the beginning, but some details were missing that I had to work out. One complication that caused most of the problems with this project would be that one of my list creating functions had a typo that lead to it pointing to the other list. Oops!
=====References=====
In performing this project, the following resources were referenced:

  * Matt Haas + Class lecture
  * C Programming Language O'Reilly Pocket Reference