# this file available at: https://arachnoid.com/files/python01/

# See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

import time
from sympy import sieve
from typing import List, Callable

def my_prime_sieve(top : int) -> List[int]:
    """Optimized sieve algorithm"""
    # declare sieve array, initial values all True
    sieve : List[bool] = [True] * top
    # declare list of prime numbers for caller
    primes : List[int] = []
    # add 2 to list
    primes.append(2)
    # search only to sqrt(top)
    sqrt_top = int(top**0.5)
    # sqrt_top must be an odd number
    if sqrt_top % 2 == 0: sqrt_top += 1
    # start search at 3, step by 2, odd numbers only
    for i in range(3,sqrt_top,2):
        # if i is prime
        if sieve[i]:
            # add i to prime list
            primes.append(i)
            # mark all multiples of i as composite
            # because each has i as a factor
            for j in range(i*i, top, i):
                sieve[j] = False
    # collect remaining primes
    for i in range(sqrt_top,top,2):
        if sieve[i]:
            # add i to prime list
            primes.append(i)
    return primes

def sympy_prime_sieve(top:int) -> List[int]:
    """Sympy.sieve library method"""
    # trigger sieve generator at top-1
    _ = top-1 in sieve # assumes "top" is an even number
    primes : List[int] = list(sieve._list)
    return primes

def show_timing(s: Callable[[int],List[int]],end : float,start : float) -> None:
    print(f'{s.__name__:22s}: {s.__doc__:38s}: {(end-start) * 1000:5.2f} ms')

functions = (
    my_prime_sieve,
    sympy_prime_sieve,
)

def main():
    top = 1_000_000
    results : List[List[int]] = []
    timings : List[float] = []
    print(f'{"Function":22s}: {"Description":38s}: {"Time"}')
    print(f'{"-" * 70}')
    for function in functions:
        start = time.time()
        sp : List[int] = function(top)
        end = time.time()
        results.append(sp) 
        show_timing(function,end,start)
        timings.append(end-start)

    print(f'\nResult lists identical: {results[0] == results[1]}')
    print(f'Primes in range 2 <= p < {top:,} : {len(results[0]):,}')
    ratio = timings[1] / timings[0]
    print(f'Comparison: optimized vs. sympy: optimized is {100 *(ratio-1):.0f}% faster.')
    if top <= 200:
        print(f'List of primes: {results[0]}')

if __name__ == "__main__":
    main()