sieve of eratosthenes Algorithm

The Sieve of Eratosthenes is an ancient Greek algorithm that efficiently finds all prime numbers up to a specified integer. It was created by the ancient Greek mathematician Eratosthenes in the 3rd century BC and is still one of the most popular algorithms for generating prime numbers today. The algorithm works by iteratively marking the multiples of each prime number, starting from the smallest prime, which is 2, and continuing until all numbers up to the given limit have been checked. The algorithm begins by creating a list of numbers from 2 to the desired limit (n). It then starts with the first number (which is 2) in the list and marks it as prime. Next, it removes all the multiples of 2 (excluding 2 itself) from the list, as they are not prime. The algorithm then moves to the next unmarked number in the list (which is 3) and marks it as prime, removing all its multiples from the list. This process is repeated for all the remaining unmarked numbers in the list until no more numbers are left to check. At the end of the algorithm, all the marked numbers in the list are prime numbers, and all the multiples of the prime numbers have been removed.
"""
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.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
Reference: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

doctest provider: Bruno Simas Hadlich (https://github.com/brunohadlich)
Also thanks Dmitry (https://github.com/LizardWizzard) for finding the problem
"""


import math


def sieve(n):
    """
    Returns a list with all prime numbers up to n.

    >>> sieve(50)
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
    >>> sieve(25)
    [2, 3, 5, 7, 11, 13, 17, 19, 23]
    >>> sieve(10)
    [2, 3, 5, 7]
    >>> sieve(9)
    [2, 3, 5, 7]
    >>> sieve(2)
    [2]
    >>> sieve(1)
    []
    """

    l = [True] * (n + 1)  # noqa: E741
    prime = []
    start = 2
    end = int(math.sqrt(n))

    while start <= end:
        # If start is a prime
        if l[start] is True:
            prime.append(start)

            # Set multiples of start be False
            for i in range(start * start, n + 1, start):
                if l[i] is True:
                    l[i] = False

        start += 1

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

    return prime


if __name__ == "__main__":
    print(sieve(int(input("Enter n: ").strip())))

LANGUAGE:

DARK MODE: