Python_sieve

python_sieve.py

import time


def measured_time(func):
    def wrapped(*args):
        start = time.perf_counter_ns()
        result = func(*args)
        elapsed = int((time.perf_counter_ns() - start) / 1000000)
        print(f'Elapsed time is {elapsed} ms')
        return result
    return wrapped


@measured_time
def sieve_Eratosphen(n) -> list[int]:
    assert n > 2
    nxt = 2
    numbers = [True for _ in range(n)]
    while nxt * nxt <= n:
        if numbers[nxt]:
            for index in range(n - nxt):
                step = nxt * nxt + index * nxt
                if step < n:
                    numbers[step] = False
                else:
                    break
        nxt += 1
    return [idx for idx, is_prime in enumerate(numbers) if idx >= 2 and is_prime]


if __name__ == '__main__':
    print(f'Last prime is {sieve_Eratosphen(100000000)[-1]}')