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))