0

**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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
jim
  • 8,670
  • 15
  • 78
  • 149
  • Are you trying to add multithreading to this? – Toast Nov 08 '11 at 14:58
  • Yes, I'm trying to add multithreading to this. [Question edited]. – jim Nov 08 '11 at 14:59
  • answering the question in title, `o = 1 + 2*div a 2` is odd start of range from `a` to `b`, and `q x = x*x - 2*x*min 0 (div (x*x-o) (2*x))` is 1st odd multiple of `x >= x*x` in range (in Haskell). Taken from http://stackoverflow.com/questions/12430495/how-do-i-reduce-the-space-complexity-in-sieve-of-eratosthenes-to-generate-prime/12497763#12497763 . – Will Ness Oct 05 '12 at 13:20

2 Answers2

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.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • Ah ok, so one thread will be solely responsible for finding primes. Then the workers will be responsible for filtering out non-primes in their respective lists? – jim Nov 08 '11 at 15:06
  • Cool, I seem to have a working solution. Am I allowed to post up here for corrections. Or should I not, as this will directly solve the problem for fellow students. [what's the policy?] – jim Nov 08 '11 at 15:38
  • @Conor - There isn't a "policy" _per se_, but it's generally discouraged to post outright answers to homework questions. The purpose of the "homework" tag is to alert posters to consider this. On the other hand, the whole reason for the forum is to get and give help with programming problems. Perhaps you can be selective about what you post and thread the needle (as the saying goes). – Ted Hopp Nov 08 '11 at 15:57
0

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.

Toast
  • 424
  • 2
  • 9