Python - Sieve of Eratosthenes implementation for multiprocessing environment
get will block. You need to write two loops. Try this:
# Count primes in each segment
processes = 
for start in xrange(2, n+1, segment_size+1):
end = start+segment_size
end = n
processes.append(pool.apply_async(countprimes, [start, end]))
for process in processes:
count += process.get()
You mess your numbering up. If
p[k] is the primeness of number
k+1, your for loop is wrong
for(int j = i*i; j < n; j += i)
and should be
for(int j = (i-1)*(i-1); j < n; j += (i-1))
My advice would be to use more informative variable names and avoid those sources of confusion like
p[k] giving information about integer
The second is more efficient. It is also the Sieve of Eratosthenes. The first algorithm is trial division, and is not the Sieve of Eratosthenes.
The first algorithm has a time complexity of O(n sqrt(n)), or perhaps a bit less if you use only primes as trial divisors. The second algorithm has a time complexity of O(n log log n), which is near-enough linear since log log n is very small.
As an experiment, compute the first million primes, up to 15485863, and see which one is faster. It won't be even close. The second algorithm will finish in a few seconds. The first algorithm will take a few hours.
Here is the other code I wrote. I will now check if this one or the other is better.
number_list, limit = [x for x in range(2,N+1)], int(math.sqrt(N))
for n in range(0, limit):
if number_list[n] != -1:
for y in range(number_list.index(number_list[n])+1, len(number_list)):
if number_list[y] != -1:
if number_list[y]%number_list[n] == 0:
number_list[y] = -1
number_list = list(set(number_list))
Ok, so this piece of code took 15.90 seconds to compute primes up to 1,000,000.
The first one that I posted took only 4.71 seconds to computer primes up to 1,000,000.
J.F. Sebastian said that if your code has division, then it's not the SOE but in order to see if each number is a multiple of the remaining numbers, you need to use the modulus operator (which basically is like division), is it not?
The last line:
multiples.update(range(i*i, n+1, i))
Adds all the multiples of
i from the square of
i up to
n to the set
multiples. Any multiple below the square of
i will already be in the set from an earlier
Rosetta doesn't say the algorithm is O(log(n)), it certainly isn't but just that set lookup is O(log(n)) vs list O(n). The reason is that sets use hashing as means of looking up and is actually on average O(1) vs. O(n)
|Login to Add Your Comments .||