Lab46 Wiki

Focused only on prime numbers Additional optimization level

Make an array, and store the prime numbers as they are discovered. Then only check your test number against those prime numbers.

\*\*I will fix these notes later - Ash

The sieve only works with prime numbers, you might find it easier just to create a separate file that contains the code for your sieve of eratosthenes. If you do, add your filename to the end of “BIN = $(PROJ)” inside of the makefile. Example: if you have a file named sieve.c, your new Makefile should read “BIN = $(PROJ) sieve”. You can test if you did it right by running make and it will show sieve.c as well as your cnv2.c file.

NOTE: Your implementation of the Sieve of Eratosthenes will likely involve the usage of exponents, likely squares. Keep in mind that the ^ operator in C does not mean exponent / power. ^ is a bitwise XOR operator. Either use the pow() function that math.h provides, or simple multiply the same variable by itself multiple times.

Prime numbers only.

You have a populated array starting from your checking value to your upper bound. You will cross out all other numbers that are divisible by the number you are checking. This will reduce the numbers you will be checking. Afterwards, move to the your checking number to the next number that is not a crossed out number, and test if that is a prime. If it is, remove that number from the list of available numbers, until you reach the upper bound. Repeat this process until either your quantity or upper bound is reached.

Here is a nice gif:

\*\*I will fix these notes later - Ash

*Our task is to ask questions on Discord or in class and document our findings on this wiki page collaboratively, regarding the functionality of this project.

*For anybody interested in editing the wiki page, here is the dokuwiki user guide: https://www.dokuwiki.org/wiki:syntax#basic_text_formatting -Ash