User Tools

Site Tools


user:dschoeff:portfolio:primalitytest

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

user:dschoeff:portfolio:primalitytest [2011/12/13 02:32] – created dschoeffuser: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/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===
 +<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                                            *
 +***************************************************************/
 +
 +#include<stdio.h>
 +#include<stdlib.h>
 +#include"queue.h"//this program utilizes my queue library
 +#include<math.h>
 +
 +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);
 +}
 +
 +
 +</code>
 +=====Execution=====
 +The execution of my code.
 +<cli>
 +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$
 +
 +</cli>
 +
 +=====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]]
 +