Prime sieve in Python I was trying to write Sieve for the first time and I came up with this code:

def sieve(num):
    numbers = set(range(3, num, 2))
    for i in range(3, int(num**(1/2)) + 1 , 2):
        num_set = set(i*c for c in range(3, num//2, 2))
        numbers = numbers - num_set
    return list(sorted((2, *numbers)))


The problem is that for num &gt; 10**6 the time to create prime numbers increases. 

Also, when I tried num = 10**8 my computer stopped working, started to make awkward noises and I had to restart it. 

I think the problem is that I am dealing with sets. For large numbers (for instance, in num = 10**8 case) the set cannot be produced since my computer cannot process that much information, hence it stops.

Is there a way to solve this memory or time problem using my code or should use a different algorithm?
Using a set() is your bottleneck, memory-wise.

&gt;&gt;&gt; numbers = set(range(3, 10**8, 2))
&gt;&gt;&gt; sys.getsizeof(numbers)
2147483872
&gt;&gt;&gt; sys.getsizeof(numbers) + sum(map(sys.getsizeof, numbers))
3547483844


A set of odd numbers up to 100 million is consuming 2GB 3.5GB (thank-you @ShadowRanger) of memory.  When you do an operation like numbers = numbers - num_set, you'll need to have 3 sets in memory at once.  One for the original set, one for the set of numbers you are removing, and one for the resulting set.  This will be greater than 4GB 7GB of memory, since some of the numbers you are removing aren't in the original set.

You don't need to realize the entire set of numbers you are removing in memory.  You could simply remove the numbers from the set one at a time:

for c in range(3, num // 2, 2):
    numbers.remove(i * c)


This is modifying the set in place, so the memory requirement will not exceed the initial 2GB of memory for the set.



Why are you looping c over range(3, num // 2, 2)?  This is doing way too much work.  The maximum value c should obtain should satisfy i*c &lt; num, since no product i*c larger than num will be in the original set.

You should instead loop over range(3, num // i + 1, 2).  This will decrease the size of the set of numbers you are removing as the prime numbers you find increase.



Why start removing primes at 3*i?  When i is 97, you've already removed multiples of 3, 5, 7, 11, 13, 17, ... up to 89. The first multiple you need to remove is 97*97.  You would then continue with 99*97, 101*97, and so on, up to num.  So the range should begin with i, not 3. 

for c in range(i, num // i + 1, 2):
    numbers.remove(i * c)


Actually, this is still too complicated.  Let's get rid of the multiplication.  This also greatly simplifies the upper limit of the range.

for multiple in range(i*i, num, 2*i):
    numbers.remove(multiple)


Or equivalently, passing a generator to difference_update to remove items in bulk, but without realizing the set of numbers to be removed in memory simultaneously.

numbers.difference_update(multiple for multiple in range(i*i, num, 2*i))




Even with all of the above changes, you still require 2GB of memory to compute the primes up to 100 million.  And since a set is unordered, you still have to sort the surviving numbers afterwards to get your ordered list of primes.

A better way is to maintain an array of flags, one per candidate number.  With 100 million candidate numbers, if each flag used only a single byte, you'd only require 100 MB of memory, a savings of a factor of 20.  And since the array of flags is ordered, no sorting of the array would be required.

The bytearray is one such structure.  It is an array of bytes.  You can store your candidates in the array as a 1, and any non-primes (multiples of other primes) as 0.

def sieve(num):
    flags = bytearray(num)      # Initially, all bytes are zero

    flags[2] = 1                # Two is prime
    for i in range(3, num, 2):
        flags[i] = 1            # Odd numbers are prime candidates

    # Find primes and eliminate multiples of those primes
    for i in range(3, int(num ** 0.5) + 1, 2):
        if flags[i]:
            for multiple in range(i * i, num, 2 * i):
                flags[multiple] = 0

    return [ i for i, flag in enumerate(flags) if flag ]




Conserving a little bit more memory, you can store your list of primes in an array

import array

def sieve(num):
    flags = bytearray(num)      # Initially, all bytes are zero

    flags[2] = 1                # Two is prime
    for i in range(3, num, 2):
        flags[i] = 1            # Odd numbers are prime candidates

    # Find primes and eliminate multiples of those primes
    for i in range(3, int(num ** 0.5) + 1, 2):
        if flags[i]:
            for multiple in range(i * i, num, 2 * i):
                flags[multiple] = 0

    return array.array('I', (i for i, flag in enumerate(flags) if flag))


For primes up to \$10^8\$, the array.array('I', ...) stores the 5.7 million primes in a mere 23MB of memory.  The list version takes a whopping 212MB.

Note: If you are using a 32-bit version of Python, you may need the type-code 'L' instead of 'I' to get storage for 4-byte integers in the array.



For the truly memory conscious, install the bitarray module.

pip3 install bitarray


In addition to using only a single bit per flag, for 1/8th the memory usage in the sieve, it allows some truly fantastic slice assignments from a single boolean scalar, which makes clearing all multiples of a prime number into a simple single statement.

import array
from bitarray import bitarray

def sieve(num):

    flags = bitarray(num)
    flags.setall(False)
    flags[2] = True                      # Two is prime
    flags[3::2] = True                   # Odd numbers are prime candidates

    for i in range(3, int(num ** 0.5) + 1, 2):
        if flags[i]:
            flags[i*i:num:2*i] = False   # Eliminate multiples of this prime

    primes = array.array('I', (i for i, flag in enumerate(flags) if flag))

    return primes


Timings:

10^3:  0.000
10^4:  0.000
10^5:  0.004
10^6:  0.051
10^7:  0.428
10^8:  4.506


Note: Updated timing info.  I just noticed I had for i in range(3, num + 1, 2) in the last implementation instead of for i in range(3, int(num ** 0.5) + 1, 2), resulting in a lot of wasted time doing nothing.

Python 3.8 Update: Using math.isqrt(num) is better than int(num ** 0.5):

    for i in range(3, math.isqrt(num) + 1, 2):