Return to Answer

Building off of what Grigory Ilizirov mentioned about the code staying in the all.remove() part for a significant amount of time here is a page with many different implementations of the Sieve in many different languages. You should start out at the Most efficient python implementation by clicking this link.

The set method is CRAZY fast. Mainly because of the 'if i not in multiples(the set)' part. set() has a very efficient way of searching for an element called a hash function. Now, how exactly python implements that is beyond me. I've seen this example (2nd comment, not the accepted one).

To quote it here:

list: Imagine you are looking for your socks in your closet, but you don't know in which drawer your socks are, so you have to search drawer by drawer until you find them (or maybe you never do). That's what we call O(n), because in the worst scenario, you will look in all your drawers (where n is the number of drawers).

set: Now, imagine you're still looking for your socks in your closet, but now you know in which drawer your socks are, say in the 3rd drawer. So, you will just search in the 3rd drawer, instead of searching in all drawers. That's what we call O(1), because in the worst scenario you will look in just one drawer.

• juliomalegria

Running:

def eratosthenes2(n):
    #Declare a set - an unordered collection of unique elements
    multiples = set()
    
    #Iterate through [2,2000000]
    for i in range(2, n+1):

        #If i has not been eliminated already 
        if i not in multiples:

            #Yay prime!
            yield i

            #Add multiples of the prime in the range to the 'invalid' set
            multiples.update(range(i*i, n+1, i))

#Now sum it up
iter = 0
ml = list(eratosthenes2(2000000))
for x in ml:
    iter = int(x) + iter
    
print(iter)

Completed almost before I could get my finger off of the 'run' button.

Building off of what Grigory Ilizirov mentioned about the code staying in the all.remove() part for a significant amount of time here is a page with many different implementations of the Sieve in many different languages. You should start out at the Most efficient python implementation by clicking this link.

The set method is CRAZY fast. Mainly because of the 'if i not in multiples(the set)' part. set() has a very efficient way of searching for an element called a hash function. Now, how exactly python implements that is beyond me. I've seen this example (2nd comment, not the accepted one).

To quote it here:

list: Imagine you are looking for your socks in your closet, but you don't know in which drawer your socks are, so you have to search drawer by drawer until you find them (or maybe you never do). That's what we call O(n), because in the worst scenario, you will look in all your drawers (where n is the number of drawers).

set: Now, imagine you're still looking for your socks in your closet, but now you know in which drawer your socks are, say in the 3rd drawer. So, you will just search in the 3rd drawer, instead of searching in all drawers. That's what we call O(1), because in the worst scenario you will look in just one drawer.

• juliomalegria

Running:

def eratosthenes2(n):
    #Declare a set - an unordered collection of unique elements
    multiples = set()
    
    #Iterate through [2,2000000]
    for i in range(2, n+1):

        #If i has not been eliminated already 
        if i not in multiples:

            #Yay prime!
            yield i

            #Add multiples of the prime in the range to the 'invalid' set
            multiples.update(range(i*i, n+1, i))

#Now sum it up
iter = 0
ml = list(eratosthenes2(2000000))
for x in ml:
    iter = int(x) + iter
    
print(iter)

Completed almost before I could get my finger off of the 'run' button.

Building off of what Grigory Ilizirov mentioned about the code staying in the all.remove() part for a significant amount of time here is a page with many different implementations of the Sieve in many different languages. You should start out at the Most efficient python implementation by clicking this link.

The set method is CRAZY fast. Mainly because of the 'if i not in multiples(the set)' part. set() has a very efficient way of searching for an element called a hash function. Now, how exactly python implements that is beyond me. I've seen this example (2nd comment, not the accepted one).

To quote it here:

list: Imagine you are looking for your socks in your closet, but you don't know in which drawer your socks are, so you have to search drawer by drawer until you find them (or maybe you never do). That's what we call O(n), because in the worst scenario, you will look in all your drawers (where n is the number of drawers).

set: Now, imagine you're still looking for your socks in your closet, but now you know in which drawer your socks are, say in the 3rd drawer. So, you will just search in the 3rd drawer, instead of searching in all drawers. That's what we call O(1), because in the worst scenario you will look in just one drawer.

• juliomalegria

Running:

def eratosthenes2(n):
    #Declare a set - an unordered collection of unique elements
    multiples = set()
    
    #Iterate through [2,2000000]
    for i in range(2, n+1):

        #If i has not been eliminated already 
        if i not in multiples:

            #Yay prime!
            yield i

            #Add multiples of the prime in the range to the 'invalid' set
            multiples.update(range(i*i, n+1, i))

#Now sum it up
iter = 0
ml = list(eratosthenes2(2000000))
for x in ml:
    iter = int(x) + iter
    
print(iter)

Completed almost before I could get my finger off of the 'run' button.

Building off of what Grigory Ilizirov mentioned about the code staying in the all.remove() part for a significant amount of time here is a page with many different implementations of the Sieve in many different languages. You should start out at the Most efficient python implementation by clicking this link.

The set method is CRAZY fast. Mainly because of the 'if i not in multiples(the set)' part. set() has a very efficient way of searching for an element called a hash function. Now, how exactly python implements that is beyond me. I've seen this example (2nd comment, not the accepted one).

To quote it here:

list: Imagine you are looking for your socks in your closet, but you don't know in which drawer your socks are, so you have to search drawer by drawer until you find them (or maybe you never do). That's what we call O(n), because in the worst scenario, you will look in all your drawers (where n is the number of drawers).

set: Now, imagine you're still looking for your socks in your closet, but now you know in which drawer your socks are, say in the 3rd drawer. So, you will just search in the 3rd drawer, instead of searching in all drawers. That's what we call O(1), because in the worst scenario you will look in just one drawer.

• juliomalegria

Running:

def eratosthenes2(n):
    #Declare a set - an unordered collection of unique elements
    multiples = set()
    
    #Iterate through [2,2000000]
    for i in range(2, n+1):

        #If i has not been eliminated already 
        if i not in multiples:

            #Yay prime!
            yield i

            #Add multiples of the prime in the range to the 'invalid' set
            multiples.update(range(i*i, n+1, i))

#Now sum it up
iter = 0
ml = list(eratosthenes2(2000000))
for x in ml:
    iter = int(x) + iter
    
print(iter)

Completed almost before I could get my finger off of the 'run' button.

Building off of what Grigory Ilizirov mentioned about the code staying in the all.remove() part for a significant amount of time here is a page with many different implementations of the Sieve in many different languages. You should start out at the Most efficient python implementation by clicking this link.

The set method is CRAZY fast. Running:

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

iter = 0
ml = list(eratosthenes2(2000000))
for x in ml:
    iter = int(x) + iter
    
print(iter)

Completed almost before I could get my finger off of the 'run' button.

Building off of what Grigory Ilizirov mentioned about the code staying in the all.remove() part for a significant amount of time here is a page with many different implementations of the Sieve in many different languages. You should start out at the Most efficient python implementation by clicking this link.

The set method is CRAZY fast. Mainly because of the 'if i not in multiples(the set)' part. set() has a very efficient way of searching for an element called a hash function. Now, how exactly python implements that is beyond me. I've seen this example (2nd comment, not the accepted one).

To quote it here:

list: Imagine you are looking for your socks in your closet, but you don't know in which drawer your socks are, so you have to search drawer by drawer until you find them (or maybe you never do). That's what we call O(n), because in the worst scenario, you will look in all your drawers (where n is the number of drawers).

set: Now, imagine you're still looking for your socks in your closet, but now you know in which drawer your socks are, say in the 3rd drawer. So, you will just search in the 3rd drawer, instead of searching in all drawers. That's what we call O(1), because in the worst scenario you will look in just one drawer.

• juliomalegria

Running:

def eratosthenes2(n):
    #Declare a set - an unordered collection of unique elements
    multiples = set()
    
    #Iterate through [2,2000000]
    for i in range(2, n+1):

        #If i has not been eliminated already 
        if i not in multiples: 

            #Yay prime!
            yield i 

            #Add multiples of the prime in the range to the 'invalid' set
            multiples.update(range(i*i, n+1, i)) 

#Now sum it up
iter = 0
ml = list(eratosthenes2(2000000))
for x in ml:
    iter = int(x) + iter
    
print(iter)

Completed almost before I could get my finger off of the 'run' button.