The sieve of Eratosthenes: An example of varying memory usage
The code that will be used is:
from pympler import asizeof
upper = 100
nums = []
primes = [] # Not really needed but helps with this exercise
for i in range(2, upper): # 0 and 1 are not candidates for prime
nums.append(i)
print('After initial setup of lists.')
print(f'Nums requires {asizeof.asizeof(nums)} bytes.\nPrimes requires {asizeof.asizeof(primes)} bytes.\nTotal memory required: {asizeof.asizeof(nums) + asizeof.asizeof(primes)} bytes.\n')
for num in nums: # Step through the list
if num != 0: # If the number has not been "crossed off",
primes.append(num) # Add it to the list of primes.
for i in range(nums.index(num), len(nums), num): # Step through the list in increments of the current value,
nums[i] = 0 # and cross off the multiples of the recently found prime.
# These next lines are the memory diagnostics
print(f'After {len(primes)} primes found:')
print(
f'Nums requires {asizeof.asizeof(nums)} bytes.\nPrimes requires {asizeof.asizeof(primes)} bytes.\nTotal memory required: {asizeof.asizeof(nums) + asizeof.asizeof(primes)} bytes.\n')
print(primes)
The graph below shows the memory usage as the programme runs. You can see the initial list of sequential numbers takes a total of over 4000 bytes but very quickly falls to just over 1500 bytes by the fifth prime and by the twenty-fifth prime, the end of the run, the original list is down to under 1000 bytes.
The list of primes grows in accordance with the explanation on the lists page.
The total memory starts at over 4000 bytes but quickly drops to below 2000 bytes and then grows slowly over time.
Last modified: 03 July 2024