Obtain primes with threads. How to divide intervals?

Question

I want to obtain all the prime numbers in the interval [min, max]. I want to do the calculus in n servers. Which is the best way to divide my initial interval in another n intervals, to manage approximately the same load in all the n servers?

---

[Optional]

---

I had an idea, but it didnt work as I expected. I assumed that all numbers are primes, so that a number i costs i instructions to verify is a prime.

If we keep in mind this method:

Then, the number of instructions to get primes in interval [1,100] is 1+2+..+99+100 = 100(1+100)/2 = 5050.

Now, if I want to do this calculus in 2 servers (n=2), I have to divide this load to each one (2525 instructions each one). The interval I want is defined by 2525 = x(1+x)/2 -> x=71.

In general terms, the general formula would be Load = (Interval(x) - Interval(x-1) + 1) * (Interval(x-1) + Interval(x)) / 2, being Load = (max - min + 1) * (min + max) / (2 * n).

Doing this, with x and y = [1:9999999] and n = 16, I have got this results:

_{(source: subirimagenes.com)}

I dont get the same time and instructions in all servers, what means this is not the way to divide the intervals.

Any idea?

Answer 1

I think you looking for a parallel approach. This is what the work stealing algorithm was designed for, aka Fork Join Pool. In fact, prime number calculation is a classic use case for work stealing because telling whether n is prime requires iterating till sqrt(n) so the bigger is n the longer it takes. So distributing them among your workers evenly and waiting for every worker to finish its job is unfair, the first core will quickly determine whether n is prime or not and sit idle and the other core will stay busy calculating bigger numbers. With work stealing the idle processor will steal work from its neighbours queues.

This implementation might be useful.