This shows you the differences between two versions of the page.
user:dschoeff:portfolio:primalitytest [2011/12/13 02:32] – created dschoeff | user:dschoeff:portfolio:primalitytest [2011/12/13 03:17] (current) – dschoeff | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ======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/ | ||
+ | |||
+ | * 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=== | ||
+ | <code 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 * | ||
+ | ***************************************************************/ | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | int main() | ||
+ | { | ||
+ | | ||
+ | int root, number, i, j, flag; | ||
+ | |||
+ | Node *start1, *end1, *start2, *end2; | ||
+ | |||
+ | | ||
+ | |||
+ | // user prompt for a number. The prompt allows them to enter a double value even though | ||
+ | // it will be cast to an 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; | ||
+ | | ||
+ | } | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | if(flag == 0) | ||
+ | { | ||
+ | | ||
+ | } | ||
+ | } | ||
+ | |||
+ | |||
+ | // | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | |||
+ | </ | ||
+ | =====Execution===== | ||
+ | The execution of my code. | ||
+ | <cli> | ||
+ | lab46: | ||
+ | Enter a value to compute (from 2 to): 30 | ||
+ | Composites: | ||
+ | Primes: | ||
+ | lab46: | ||
+ | |||
+ | </ | ||
+ | |||
+ | =====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:// | ||
+ | |||