======Primality Test Program====== A project for Data Structures by Dave Schoeffler during the Fall 2011 semester. This project was begun on December 7th and completed on December 9th. =====Objectives===== The point of this project is to successfully create an algorithm that finds the prime numbers between 2 and another given number. =====Prerequisites===== In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved: * Understanding the C programming language * Be familiar with my Queue library =====Background===== This project will help expand my experience of creating an algorithm to perform a certain task. This goes far beyond just writing an algorithm to test if a number is prime or not. This project will help build my experience with being confronted with a problem and finding a solution. A number is prime if its only factors are 1 and the number itself. To test for primality you must modulus divide the given number by 2 up to the square root of the number. If at any point the modulus returns a zero, the number is composite. If not the number is prime. =====Scope===== My program will function as follows. It will accept a positive integer greater than two. I will then run that number through the algorithm that I will write that determines if it is prime or not. It will store all the prime numbers between 2 and that number in a queue. If the number is not prime it will store the number in a composite number queue. Once the algorithm is done it will display both queues. =====Attributes===== The following attributes will be used in my program. * pointers: A pointer will be used to mark the beginning of the array * malloc/new: You must allocate memory for the array] * Doubly Linked lists: My queue library utilizes doubly linked lists * Queues: this program utilize my queue library * libraries: This program uses a non core libc library =====Code===== ===0x3.c=== /*************************************************************** * Author: Dave Schoeffler * * Purpose: This program will accept as in put a number. I will * * calculate all of the prime numbers between 2 and that given * * number. Once it finds a prime number it will store that * * number in a queue. If the number is not prime it will store * * that value in a queue. At the end it will display the prime * * number queue and the composite number queue. * * * * To Compile: gcc -o 0x3 0x3.c -lqueue -L. -ldll -L. -lm * * * * To Execute: ./0x3 * ***************************************************************/ #include #include #include"queue.h"//this program utilizes my queue library #include int main() { double input; int root, number, i, j, flag; Node *start1, *end1, *start2, *end2; start1 = end1 = start2 = end2 = NULL; // user prompt for a number. The prompt allows them to enter a double value even though // it will be cast to an int. printf("Enter a value to compute (from 2 to): "); scanf("%lf", &input); //calculating the square root of the input and casting it to nearest int // root = (int)(sqrt(input)); number = (int)(input);//casting input to nearest int // The folling nested for loops perform logic behind determining whether or not // a number is prime. A number is prime if it does not evenly divide by any of the // numbers between 2 and the square root of the number. for(i = 2; i < number ; i++) { root = (int)(sqrt(i)); flag = 0; for(j = 2; j < root + 1 ; j++) { if((i % j) == 0) { if((i != 2) && ( i != 3)) { flag = 1; enqueue(&start1, &end1, 0, i); } break; } } if(flag == 0) { enqueue(&start2, &end2, 0, i); } } //display the two queues printf("Composites: "); display(&start1); printf("\nPrimes: "); display(&start2); printf("\n"); return (0); } =====Execution===== The execution of my code. lab46:~/src/data/eoce/0x3$ ./0x3 Enter a value to compute (from 2 to): 30 Composites: 28 -> 27 -> 26 -> 25 -> 24 -> 22 -> 21 -> 20 -> 18 -> 16 -> 15 -> 14 -> 12 -> 10 -> 9 -> 8 -> 6 -> 4 -> Primes: 29 -> 23 -> 19 -> 17 -> 13 -> 11 -> 7 -> 5 -> 3 -> 2 -> lab46:~/src/data/eoce/0x3$ =====Reflection===== This project really made me think about how to approach a problem from scratch. I ran into a few problems that I had to fight through but in the end I was able to get everything working properly. =====References===== In performing this project, the following resources were referenced: * Matthew Haas * My Queue Library -> [[http://lab46.corning-cc.edu/user/dschoeff/portfolio/libqueue]]