codingdir logo sitemap sitemap |

Python - Sieve of Eratosthenes implementation for multiprocessing environment

By : , Category : python

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 = (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 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 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.

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))
    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)


Message :
Login to Add Your Comments .
How to disable registered OpenCL platforms on Windows?
Is Observable broken in Angular 2 Beta 3?
Cross-thread operation not valid when using Invoke
How to pass an IEnumerable or queryable list of properties from Controller to View
Finding numbers after a certain keyword using Python
Pocketsphinx recognizes random phrases in a silence
Passing non-thread-safe objects through thread-safe containers
React scroll nav
BizTalk WCF-BasicHttp Adapter does not allow Empty string for Service Certificate Props
Why property ''cause" of Exception is repeating forever?
Privacy Policy 2017 © All Rights Reserved .