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
from __future__ import annotations

import math


def prime_sieve(num: int) -> list[int]:
    """
    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 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 start is a prime
        if sieve[start] is True:
            prime.append(start)

            # Set multiples of start be False
            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())))
