Sieve of Eratosthenes

Algorithms

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a given limit $n$ .

Algorithm

The algorithm marks multiples of each prime number starting from 2, and the unmarked numbers are primes.

Time Complexity

The time complexity is $O (n lo g lo g n)$ , making it one of the most efficient algorithms for generating primes.

Implementation

def sieve_of_eratosthenes(n):
    """Return a list of all prime numbers up to n using the Sieve of Eratosthenes."""
    if n < 2:
        return []

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime numbers

    for start in range(2, int(n**0.5) + 1):
        if is_prime[start]:
            for multiple in range(start*start, n + 1, start):
                is_prime[multiple] = False

    primes = [num for num, prime in enumerate(is_prime) if prime]
    return primes

# Example usage:
n = 30
primes = sieve_of_eratosthenes(n)
print("Prime numbers up to {} are: {}".format(n, primes))