Optimising Sieve & Segmented Sieve

Lecture 88:- Optimising Sieve & Segmented Sieve

Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given limit 'n'. Segmented Sieve is an optimization of the original Sieve, which allows us to find primes in a specific range [l, r].

1. Optimizing Sieve of Eratosthenes: The basic Sieve of Eratosthenes algorithm goes as follows:

pythonCopy code

def sieve_of_eratosthenes(n):    prime = [True] * (n + 1)    p = 2    while p * p <= n:        if prime[p] == True:            for i in range(p * p, n + 1, p):                prime[i] = False        p += 1        primes = [p for p in range(2, n + 1) if prime[p]]    return primes

This implementation finds all prime numbers up to 'n' in O(n log log n) time complexity.

1. Optimizing Segmented Sieve: Segmented Sieve allows us to find prime numbers in a specific range [l, r]. It uses the concept of the Sieve of Eratosthenes but applies it to smaller segments of the range.

pythonCopy code

import math def simple_sieve(limit, primes):    prime = [True] * (limit + 1)    p = 2    while p * p <= limit:        if prime[p] == True:            for i in range(p * p, limit + 1, p):                prime[i] = False        p += 1    for p in range(2, limit + 1):        if prime[p]:            primes.append(p) def segmented_sieve(l, r):    limit = int(math.sqrt(r)) + 1    primes = []    simple_sieve(limit, primes)    n = r - l + 1    mark = [True] * n    for i in range(len(primes)):        loLim = int(math.floor(l / primes[i])) * primes[i]        if loLim < l:            loLim += primes[i]        for j in range(loLim, r + 1, primes[i]):            mark[j - l] = False    result = [l + i for i in range(n) if mark[i]]    return result

This implementation finds all prime numbers in the range [l, r] in O((r - l + 1) * log log r) time complexity.

Both the optimized Sieve of Eratosthenes and the Segmented Sieve are important tools when working with prime numbers and are frequently used in competitive programming and other algorithmic tasks.