To apply your skills in the implementation of prime number calculating algorithms.

In addition to the new skills required on previous projects, to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

• ability to make decisions (if statement)
• ability to iterate sections of code (for/while statement)

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 increasing 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 3 prime number programs:

1. brute force prime calculation
2. square root-optimized brute force calculation
3. a further optimized solution

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 1 and 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.

There is no further need to check the remaining values, as once we have proven the non-primality of a number, the state is set: it is composite. So be sure to use a break statement to terminate the computation loop (will also be a nice boost to runtime).

An optimization to the computation of prime numbers is the square root trick. Basically, if we've processed numbers up to the square root of the number we're testing, and none have proven to be evenly divisible, we can also assume primality and bail out.

The C library has a sqrt() function available through including the math.h header file, and linking against the math library at compile time (add -lm to your gcc line).

To use sqrt(), we pass in the value we wish to obtain the square root of, and assign the result to an int:

int x = 25;
int y = 0;
 
y = sqrt(x);
 
// y should be 5 as a result

For instance, the number 37 (using the square root optimization), we find the square root (whole number) of 37 is 6, so we only need to check 2-6:

37 % 2 = 1 (2 is not a factor of 37)
37 % 3 = 1 (3 is not a factor of 37)
37 % 4 = 1 (4 is not a factor of 37)
37 % 5 = 2 (5 is not a factor of 37)
37 % 6 = 1 (6 is not a factor of 37)

Because none of these values evenly divides, we can give 37 a pass: it is a prime

This will dramatically improve the runtime, and offers a nice comparison against our brute force baseline.

There are many other methods, approaches, and tweaks that can be employed to further improve runtime (while maintaining accuracy– all your solutions must match: the same prime numbers should be identified no matter which program is run).

So I'd like you to explore other optimizations that can be made, be it using other prime number algorithms, further refining existing ones, or playing off patterns in numbers.

One assumption I will allow you to make for your optimized solution is that the single-digit primes (2, 3, 5, 7) can be assumed prime, and just printed out if having them be calculated would otherwise break your algorithm (might be helpful to some people; I certainly found it useful in some of my solutions).

It is your task to write 3 separate prime number calculating programs:

1. primebrute.c: for your brute force implementation
2. primesqrt.c: for your square root-optimization of the brute force
3. primeopt.c: for your optimized solution, be it basing off the existing ones, or taking a different approach

Your program should:

• obtain 2 parameters from the command-line (see command-line arguments section below):
  • argv[1]: maximum value to calculate to (your program should run from (approximately) 2 through that number (inclusive of that number)
  • argv[2]: visibility. If a 1 is provided, print out the prime numbers in a space separated list; if a 0 is provided, run silent: only display the runtime information.
  • these values should be positive integer values; you can make the assumption that the user will always do the right thing.
• start your stopwatch (see timing section below):
• perform the correct algorithm against the input
• if enabled, display the prime numbers found in the range
• output the processing run-time to STDERR (do this always).
• your output MUST be conformant to the example output in the execution section below. This is also a test to see how well you can implement to specifications. Basically:
  • if primes are being displayed, they are space-separated (first prime hugs the left margin), and when all said and done, a newline is issued.
  • the timing information will be displayed in accordance to code I will provide (in the timing section).

Often times, when checking the efficiency of a solution, a good measurement (especially for comparison), is to time how long the processing takes.

In order to do that in our prime number programs, we are going to use C library functions that obtain the current time, and use it as a stopwatch: we'll grab the time just before starting processing, and then once more when done. The total time will then be the difference between the two (end_time - start_time).

We are going to use the gettimeofday(2) function to aid us in this, and to use it, we'll need to do the following:

In order to use the gettimeofday(2) function in our program, we'll need to include the sys/time.h header file, so be sure to add it in with the existing ones:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

gettimeofday(2) uses a struct timeval data type, of which we'll need to declare two variables in our programs (one for storing the starting time, and the other for the ending time).

Please declare these with your other variables, up at the top of main() (but still WITHIN main()– you do not need to declare global variables).

    struct timeval time_start; // starting time
    struct timeval time_end;   // ending time

To use gettimeofday(2), we merely place it at the point in our code we wish to take the time.

For our prime number programs, you'll want to grab the start time AFTER you've declared variables and processed arguments, but JUST BEFORE starting the driving loop doing the processing.

That call will look something like this:

    gettimeofday(&time_start, 0);

The ending time should be taken immediately after all processing (and prime number output) is completed, and right before we display the timing information to STDERR:

    gettimeofday(&time_end, 0);

Once we having the starting and ending times, we can display this to STDERR. You'll want this line:

    fprintf(stderr, "%10.6lf\n", time_end.tv_sec - time_start.tv_sec + ((time_end.tv_usec - time_start.tv_usec) / 1000000.0));

And with that, we can compute an approximate run-time of our programs. The timing won't necessarily be accurate down to that level of precision, but it will be informative enough for our purposes.

Several operating behaviors are shown as examples.

Brute force showing primes:

lab46:~/src/cprog/pnc0$ ./primebrute 90 1
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 
  0.000088
lab46:~/src/cprog/pnc0$ 

Brute force not showing primes:

lab46:~/src/cprog/pnc0$ ./primebrute 90 0
  0.000008
lab46:~/src/cprog/pnc0$ 

Similarly, for the square root version (showing primes):

lab46:~/src/cprog/pnc0$ ./primesqrt 90 1
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 
  0.000089
lab46:~/src/cprog/pnc0$ 

And, without showing primes:

lab46:~/src/cprog/pnc0$ ./primesqrt 90 0
  0.000006
lab46:~/src/cprog/pnc0$ 

Don't be alarmed by the visible square root actually seeming to take MORE time; we have to consider the range as well: 90 is barely anything, and there is overhead incurred from the sqrt() function call. The real savings will start to be seen once we get into the thousands (and beyond).

And that's another neat thing with algorithm comparison: a “better” algorithm may have a sweet spot or power band: they may actually perform worse until (especially at the beginning).

The same goes for your optimized solution (same parameters).

The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate.

There will be an additional bonus point opportunity with this project, based on processing run-time of your optimized solution.

To successfully complete this project, the following criteria must be met:

• Code must compile cleanly (no warnings or errors)
• Output must be correct, and match the form given in the sample output above.
• Code must be nicely and consistently indented (you may use the indent tool)
• Code must utilize the algorithm(s) presented above:
  • primebrute.c must do the unoptimized brute force method
  • primesqrt.c must utilize the brute force method along with the square root trick (no other tricks)
  • primeopt.c is your attempt at optimizing the code, using whatever additional tricks (or enhancements to tricks) to further improve runtime.
• Code must be commented
  • have a properly filled-out comment banner at the top
    • be sure to include any compiling instructions
  • have at least 20% of your program consist of //-style descriptive comments
• Output Formatting (including spacing) of program must conform to the provided output (see above).
• Track/version the source code in a repository
• Submit a copy of your source code to me using the submit tool.

To submit this program to me using the submit tool, run the following command at your lab46 prompt:

$ submit cprog pnc0 primebrute.c primesqrt.c primeopt.c
Submitting cprog project "pnc0":
    -> primebrute.c(OK)
    -> primesqrt.c(OK)
    -> primeopt.c(OK)

SUCCESSFULLY SUBMITTED

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.