sieve of eratosthones the sieve of eratosthenes is an algorithm used to find prime numbers less than or equal to a given value illustration https upload wikimedia orgwikipediacommonsbb9sieveoferatosthenesanimation gif reference https en wikipedia orgwikisieveoferatosthenes doctest provider bruno simas hadlich https github combrunohadlich also thanks to dmitry https github comlizardwizzard for finding the problem returns a list with all prime numbers up to n primesieve50 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 primesieve25 2 3 5 7 11 13 17 19 23 primesieve10 2 3 5 7 primesieve9 2 3 5 7 primesieve2 2 primesieve1 if start is a prime set multiples of start be false returns a list with all prime numbers up to n prime_sieve 50 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 prime_sieve 25 2 3 5 7 11 13 17 19 23 prime_sieve 10 2 3 5 7 prime_sieve 9 2 3 5 7 prime_sieve 2 2 prime_sieve 1 if start is a prime set multiples of start be false
from __future__ import annotations

import math


def prime_sieve(num: int) -> list[int]:
    

    if num <= 0:
        msg = f"{num}: Invalid input, please enter a positive integer."
        raise ValueError(msg)

    sieve = [True] * (num + 1)
    prime = []
    start = 2
    end = int(math.sqrt(num))

    while start <= end:
        
        if sieve[start] is True:
            prime.append(start)

            
            for i in range(start * start, num + 1, start):
                if sieve[i] is True:
                    sieve[i] = False

        start += 1

    for j in range(end + 1, num + 1):
        if sieve[j] is True:
            prime.append(j)

    return prime


if __name__ == "__main__":
    print(prime_sieve(int(input("Enter a positive integer: ").strip())))