Using a set()
is your bottleneck, memory-wise.
>>> numbers = set(range(3, 10**8, 2))
>>> sys.getsizeof(numbers)
2147483872
>>> 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 < 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, num, 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.001
10^5: 0.014
10^6: 0.107
10^7: 0.987
10^8: 9.701
//
implies 3 to me, but I'd like that confirmed. \$\endgroup\$ – Fund Monica's Lawsuit Jun 18 at 20:09*numbers
uses the unpacking operator, which is only in Python3 \$\endgroup\$ – user122352 Jun 18 at 20:45