eratosthenesSieve.py

from math import ceil, sqrt
def EratosthenesSieve(N:int)-> list:
    '''
    Calculating SPF (Smallest Prime Factor) for every number till N.
    Time Complexity : O(NloglogN)
    '''
    N+=1
    # stores smallest prime factor for every number
    spf = [*range(N)]
    
    # separately marking spf for every even number as 2 
    for i in range(4, N, 2):
        spf[i] = 2
    for i in range(3, ceil(sqrt(N))): 
        # checking if i is prime
        if (spf[i] == i):
            # marking SPF for all numbers divisible by i
            for j in range(i * i, N, i):
                # marking spf[j] if it is not previously marked 
                if (spf[j] == j):
                    spf[j] = i
    return spf