# pico_sieve.py
# Raspberry Pi Pico - Sieve of Eratosthenes demo
# Calculate all the prime numbers within a range of low integers. Note that
# this is purely computational; nothing depends specifically on CircuitPython,
# and this works fine in a normal desktop Python 3 as well.
import time
import math
size = 40000
# Capture an initial time stamp to compute runtime.
start = time.monotonic()
# Array of boolean flags, one per integer. A True represents a possible prime number,
# a False a composite number.
flags = [True]*size
# Walk up through the array, identifying all prime numbers and removing their
# multiples from the set of integers by setting the corresponding flag to False.
# Note that the scan can stop once values are reached for which no unique
# multiples are included in the array.
for i in range(2, int(math.sqrt(size))):
if flags[i] is True:
# This value is a prime, now remove all the multiples from the set.
# Note that this marking may begin at i*i since all lower multiples will
# have already been removed.
multiple = i * i
while multiple < size:
flags[multiple] = False
multiple += i
# Capture an final time stamp to compute runtime.
end = time.monotonic()
# Any remaining True values are prime
print("Prime numbers:")
for i in range(2, size):
if flags[i] is True:
print(i)
print("Sieve running time:", end - start, "seconds.")