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.

The point of this project is to successfully create an algorithm that finds the prime numbers between 2 and another given number.

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

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.

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.

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

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

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$

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.

In performing this project, the following resources were referenced:

• Matthew Haas
• My Queue Library → http://lab46.corning-cc.edu/user/dschoeff/portfolio/libqueue