Retrieve the next minimum element of the Python set

# Compute all prime numbers less than k using the Sieve of Eratosthenes
def sieve(k):
 s = set(range(3, k, 2))
 s.add(2)

 for i in range(3, int(sqrt(k)), 2):
 if i in s:
 for j in range(i ** 2, k, i * 2):
 s.discard(j)

 return sorted(s)

for i in range(3, int(sqrt(k)), 2):
 if i in s:
 [...] 

while i < sqrt(k):
 [...]
 i = next smallest element in s

Sieve of Eratosthenes is a fairly fast way to generate prime numbers, as shown below:

>from the set p = (2,3,4,…,k) start, i = 2.
>Start from i^2, delete all multiples of i from p.
> Repeat for the next smallest i in p, Until i> = sqrt(k).

My current implementation looks like this (obviously optimizes pre-filtering all even numbers):

# Compute all prime numbers less than k using the Sieve of Eratosthenes
def sieve(k):
 s = set(range(3, k, 2))
 s.add(2)

 for i in range(3, int(sqrt(k)), 2):
 if i in s:
 for j in range(i ** 2, k, i * 2):
 s.discard(j)

 return sorted(s)

Edit: This is the code based on the equivalent list:

def sieve_list(k): 
 s = [True] * k
 s[0] = s[1] = False
 for i in range(4, k, 2):
 s[i] = False

 for i in range(3, int(sqrt(k)) + 2, 2):
 if s[i]: 
 for j in range(i ** 2, k, i * 2):
 s[j] = False

 return [2] + [i for i in range(3, k, 2) if s[ i] ]

This works, but it’s not completely correct. Lines:

for i in range(3, int(sqrt(k)), 2):
 if i in s:
 [...]

Find the next smallest element of s by testing each odd set membership. Ideally, The implementation should be:

while i  [...]
 i = next smallest element in s

However, since the set is unordered, I don’t know how (or even possible) to get the next smallest element in a more efficient way. I have considered using a list with True/False flags for prime number processing, but You still need to traverse the list to find the next True element. Not only can you actually delete the element from the list, because then you can’t effectively delete the compound number in step 2.

Is there a way to find the next element more efficiently? A smallest element? If not, are there other data structures that allow an efficient way to delete O(1) by value and find the next smallest element?

Sets are unordered because they are implemented internally as hash sets. It is inefficient to find the smallest element in this data structure ; min(s) will be the scariest way (but it is O(n)).

You can use collections.deque with your collection. Use deque to store in sorted order List of elements. Whenever you need to get the minimum value, you can pop elements in the deque until you find an element in the set. This will spread the O(1) cost across the entire input array (because you only need to pop n times) .

I should also point out that there is no data structure to create O(n) from a list (or O(1) insertion), delete O(1) and O(1) minimum search by value; Such a data structure can be used to simply implement O(n) general sorting, which is impossible (in information theory). The hashset is very close, but the effective minimum must be sacrificed.