Corning Community College
CSCS2650 Computer Organization
To apply your skills in the implementation of several prime number computing algorithms across varying languages and utilizing various forms of optimization.
In mathematics, a prime number is a value that is only evenly divisible by 1 and itself; it has no other factors. Numbers that have divisibility/factors are known as composite numbers.
The number 6 is a composite value, as in addition to 1 and 6, it also has the factors of 2 and 3.
The number 17 is a prime number, as no numbers other than 1 and 17 can be evenly divided.
As of yet, there is no quick and direct way of determining the primality of a given number. Instead, we must perform a series of tests to determine if it fails primality (typically by proving it is composite).
This process incurs a considerable amount of processing overhead on the task, so much so that increasingly large values take ever-expanding amounts of time. Often, approaches to prime number calculation involve various algorithms, which offer various benefits (less time) and drawback (more complex code).
Your task for this project is to implement a prime number program using the straightforward, unoptimized brute-force algorithm.
The brute force approach is the simplest to implement (and likely also the worst-performing). We will use it as our baseline (it is nice to have something to compare against).
To perform it, we simply attempt to evenly divide all the values between 2 and one less than the number in question. If any one of them divides evenly, the number is NOT prime, but instead a composite value.
Checking the remainder of a division indicates whether or not a division was clean (having 0 remainder indicates such a state).
For example, the number 11:
11 % 2 = 1 (2 is not a factor of 11) 11 % 3 = 2 (3 is not a factor of 11) 11 % 4 = 3 (4 is not a factor of 11) 11 % 5 = 1 (5 is not a factor of 11) 11 % 6 = 5 (6 is not a factor of 11) 11 % 7 = 4 (7 is not a factor of 11) 11 % 8 = 3 (8 is not a factor of 11) 11 % 9 = 2 (9 is not a factor of 11) 11 % 10 = 1 (10 is not a factor of 11)
Because none of the values 2-10 evenly divided into 11, we can say it passed the test: 11 is a prime number
On the other hand, take 119:
119 % 2 = 1 (2 is not a factor of 119) 119 % 3 = 2 (3 is not a factor of 119) 119 % 4 = 3 (4 is not a factor of 119) 119 % 5 = 4 (5 is not a factor of 119) 119 % 6 = 5 (6 is not a factor of 119) 119 % 7 = 0 (7 is a factor of 119)
Because 7 evenly divided into 119, it failed the test: 119 is not a prime, but instead a composite number.
Even though you have identified the number as a composite, you MUST CONTINUE evaluating the remainder of the values (up to 119-1). It might seem pointless (and it is for a production program), but I want you to see the performance implications this creates.
Measuring time can help us determine the efficiency of the program because we can determine if the runtime was faster or not.
In order to use the gettimeofday(2) function, we need to include sys/time.h in our program.
#include <stdio.h> #include <stdlib.h> #include <sys/time.h>
The prototype for this function is as follows:
int gettimeofday(struct timeval *tv, struct timezone *tz);
Since we need a place to store in the values and the parameter that stores the value is a struct timeval datatype, we need to declare the variable as follows:
struct timeval time_start; // starting time struct timeval time_end; // ending time
First, we need to set up our initial time. We can do this by doing a call something like this:
gettimeofday(&time_start, 0);
We would want to put this at the start of our program after all the declaration and error checking BUT before the main algorithm. Now that we have our starting time, we would also need a ending time. This call should be after all the processing is complete, and before we display the timing information to STDERR.
gettimeofday(&time_end, 0);
Now that we got both starting and ending time, all we need to do is print out the difference in time. You can display this by using the following:
fprintf (stderr, "%8.4lf\n", time_end.tv_sec-time_start.tv_sec+((time_end.tv_usec-time_start.tv_usec)/1000000.0));
You must write AT LEAST 5 of the choices below.
primereg.c / primeregb.c / primeregs.c / primeregbs.c are all REQUIRED
Brute Force - This is the no optimization method. Check 2 - quantity and check all factors of the prime as stated ABOVE. You do NOT break once you find a number is prime you continue through checking every single check. For example: 25 will check all numbers from 2 - 24, you will not break once you get to 5.
Break on composite - Once you can determine a number is NOT prime you can break from the the rest of the checks. For example if you are checking if 25 is a prime number, you can start by checking if 2 is a factor of 20 then 3, 4, and 5. Once you hit 5 you see this is NOT prime. Then you do not need to calculate the rest of the checks: 6, 7, 8, 9 etc…
Square root trick - You can use the <math.h> include file with sqrt() function or approximate the square root process using logic (this could potentially save runtime because you are not checking as many things as the sqrt function would check through). The premisis is that you only need to check factors of a number up until the Square root of that number. For example the square root of 25 is 5. This tells us that you only need to check factors 2 through 5 to find if this number is a prime or not.
#include <math.h>
sqrt()-less square root approximation (a)- This is optional, you would do this instead of the sqrt() function. (If you've taken discrete then you know how to do it, if you haven't taken discrete and are looking for moar then this is an option.) The sqrt function in the math library does an exact calculation of a square root. Since we are only dealing with whole numbers for our prime project it is possible to create your own logic to approximate the square root. Since the sqrt function will run for every number that is being checked you are looking at quite a performance increase.
primereg.c - baseline program (Brute force, no break)
primeregs.c - baseline, plus square root trick (Use <cmath> or <math.h> header for sqrt())
primeregb.c - baseline, plus break on composite
primeregbs.c - baseline, plus square root trick, plus break on composite
Choice of A, R, or L
primeregAbs.c - baseline, array, square root trick, break on composite
Note: (Store prime divisors into array and check against the array)
Array size(amount of elements) == argument 1(number of primes)
primeregRbs.c - Recursive brain melter ?
primeregLbs.c - Linked List - similar to primeregAbs - save primes in a linked list rather than an array. Also include the break on composite and square root trick.
lab46:~/src/comporg/pnc0/gcc$ ./primereg 8 2 3 5 7 11 13 17 19 0.0001 lab46:~/src/comporg/pnc0/gcc$
The primereg files will take One argument. That argument (argv[1]) will be for QUANTITY.
Clarification: How many primes (starting from 2) that you want to print.
-Put all c files in gcc directory from pnc0 grabit
-Numbers go to stderr, time goes to stdout
To test your output of STDERR vs STDOUT:
Redirect your STDERR to /dev/null to only output the STDOUT to terminal
lab46:~/src/comporg/pnc0/gcc$ ./primereg 8 2> /dev/null 0.0001 lab46:~/src/comporg/pnc0/gcc$
Redirect your STDOUT to /dev/null to only output the STDERR to terminal
lab46:~/src/comporg/pnc0/gcc$ ./primereg 8 > /dev/null 2 3 5 7 11 13 17 19 lab46:~/src/comporg/pnc0/gcc$
To test your output time tests you can do the following:
lab46:~/src/comporg/pnc0$ ./pncrun
Also do not forget about error checking!
EXAMPLE:
lab46:~/src/comporg/pnc0/gcc$ ./primereg Incorrect Number of Arguments! ./primereg QUANTITY lab46:~/src/comporg/pnc0/gcc$
To submit, run:
lab46:~/src/comporg/pnc0$ make submit
if you run into trouble edit the makefile and on line 47 where it says “save: clean” remove the word “clean”
Also you can try
lab46:~/src/comporg/pnc0$ make update