segmented sieve Algorithm

The segmented sieve algorithm is an optimized version of the sieve of Eratosthenes, a popular method to find all prime numbers within a given range. The primary motivation behind the segmented sieve algorithm is to reduce the memory requirements while still maintaining the efficiency of the original sieve. The algorithm works by breaking down the given range into smaller segments and sieving each segment individually, hence the name "segmented" sieve. To execute the segmented sieve algorithm, start by finding all the prime numbers up to the square root of the given upper limit. These prime numbers are then used as the base of sieving for the remaining segments. By sieving each segment, we eliminate the non-prime numbers within the segment, leaving behind only the prime numbers. Since the algorithm processes one segment at a time, it significantly lowers the memory consumption compared to the traditional sieve of Eratosthenes. Additionally, the segmented sieve algorithm maintains efficiency by leveraging previously computed primes, making it an ideal choice for scenarios where memory constraints are critical, such as in embedded systems or competitive programming.
"""Segmented Sieve."""

import math


def sieve(n):
    """Segmented Sieve."""
    in_prime = []
    start = 2
    end = int(math.sqrt(n))  # Size of every segment
    temp = [True] * (end + 1)
    prime = []

    while start <= end:
        if temp[start] is True:
            in_prime.append(start)
            for i in range(start * start, end + 1, start):
                if temp[i] is True:
                    temp[i] = False
        start += 1
    prime += in_prime

    low = end + 1
    high = low + end - 1
    if high > n:
        high = n

    while low <= n:
        temp = [True] * (high - low + 1)
        for each in in_prime:

            t = math.floor(low / each) * each
            if t < low:
                t += each

            for j in range(t, high + 1, each):
                temp[j - low] = False

        for j in range(len(temp)):
            if temp[j] is True:
                prime.append(j + low)

        low = high + 1
        high = low + end - 1
        if high > n:
            high = n

    return prime


print(sieve(10 ** 6))

LANGUAGE:

DARK MODE: