Sieve of Erathostenes.. find primes in range. How to get starting point?

Question

**NOTE: This is related to a college assignment. I'm only requesting some guidance in the right direction.

I have a single threaded solution to find prime numbers (Homework is to convert to multi threaded solution). It currently says to start off with the list of numbers to be checked. Starting with the first prime, 2. (for 0...N).

I want to be able to divide up the list (0...N) to something like (0...25), (26...50), (51...75) and (76...100).

If the starting point for each list is the first prime. How do I find it? Must I have a seperate function to get that?

Thanks.

Answer 1

I take it that you want a multi-threaded implementation. You don't need each list to start with a prime. (That would actually be a bit circular, considering what you're trying to compute.) Think of a group of workers, each with a list. Rather than have each worker work in isolation, think of broadcasting the current prime against which to sieve and have each worker go off and apply it to that worker's list. Wait until every worker reports completion of that phase, find the next prime, and repeat.

Answer 2

To add multithreading, I would just use a variable to keep track of what number the sieve is up to, and start a thread to remove the multiples of those numbers.

int a = 2;
//run thread 1
while(sieve[a] == false)
    a++;
//run thread 2
//etc.

Obviously there's a little more to it.. but this is the general idea.