# 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,gc
SIZE = 180_000

# Capture an initial time stamp to compute runtime.
start = time.ticks_ms()

print('START')

# Array of boolean flags, one per integer.  A True represents a possible prime number,
# a False a composite number.
flags = bytearray(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.

@micropython.viper
def check(size:int):
  f=ptr8(flags)
  for i in range(2, size):
      if int(f[i]) == 0:
          # this value is a prime, now remove all the multiples from the set
          multiple = 2 * i
          while multiple < size: #SIZE:
              f[multiple] = 1
              multiple += i
check(SIZE)
# Capture an final time stamp to compute runtime.
end = time.ticks_ms()
print('STOP')

# Any remaining True values are prime
print("Prime numbers:")

for i in range(2, SIZE):
    if flags[i] == 0:
      pass
      #print(i)

print("Sieve running time:", (end - start)/1000, "seconds.")
print(gc.mem_free())