2018-10-18 - Sieve of Eratosthenes

posted Oct 18, 2018, 12:13 PM by Konstantinovich Samuel   [ updated Oct 19, 2018, 11:57 AM ]
You must use the sieve of Eratosthenes, not some other algorithm. 

You are eliminating the multiples of each prime, then finding the next non-eliminated number which must be prime, and repeating.
Eliminate multiples of  2 (but not 2),
3 is next, eliminate multiples of 3,
then the multiples of 5 etc.

Whatever has not been eliminated (white in the picture) is prime. Note that you just need a prime/not-prime state, don't worry what divides the number.

Kontest Requirements:

Submit by Thursday October 25th Morning
Submit a link to your repo here: (ONLY if you want to enter the competition)

1. You must make a repo and place sieve.h and sieve.c inside that directory, not a subdirectory:

2. Your sieve.h should have the function:
  int sieve(int targetPrime);

3. There should be no printed output when sieve() is called!

I will use a driver of mine.
I will compile with the -lm flag so you can use math.h.

K-specific requirements:

 name your repo:

In your makefile, you can pass args to the program:

    ./primetest $(args)

Then you can use the shell as follows:
make run args="100000 10"

Feel free to use this driver file in your testing:

#include <stdio.h>
#include <stdlib.h>
#include "sieve.h" int main(int argc, char * argv[]){ int iterations = 1; int target = 1000000; if(argc > 1){ target = atoi(argv[1]); } if(argc > 2){ iterations = atoi(argv[2]); } int ans = 0; while(iterations>0){ ans=sieve(target); iterations--; printf("The n=%d prime is %d\n", target, ans );
//this is to modify which prime to //potentially avoid CPU caching target++; } return 0; }