Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======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]]
Lab46 Wiki

User Tools

Site Tools

Page Tools
