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.

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.

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

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)

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.

• 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

/*
 * 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");
}

This is how to compile and execute:

lab46:~/src/data/prime$ gcc -o prime main.c
lab46:~/src/data/prime$ ./prime

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!

In performing this project, the following resources were referenced:

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