Python  Sieve of Eratosthenes implementation for multiprocessing environment
The 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
if end>n:
end = n
processes.append(pool.apply_async(countprimes, [start, end]))
for process in processes:
count += process.get()
ReLated : 
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 = (i1)*(i1); j < n; j += (i1))
My advice would be to use more informative variable names and avoid those sources of confusion like p[k] giving information about integer k+1 .

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 nearenough 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.
import math
def primes(N):
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))
number_list.remove(1)
number_list.sort()
return 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 i .
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)

Comments
Message : 
Login to Add Your Comments . 

