Модифицированное сито Эратосфена во временной сложности O(n), объясненное кодом Python

 1.For every number i where i varies from 2 to N-1:
     Check if the number is prime. If the number
     is prime, store it in an array.
 2.For every prime numbers j less than or equal to the smallest prime factor (SPF) p of i:
     Mark all numbers j*p as non_prime.
     Mark smallest prime factor of j*p as j.

def modified_seive(N):
    # isPrime[] : isPrime[i] is true if number i is prime
    # initialize all numbers as prime numbers
    isprime = [True] * N
    # 0 and 1 are not prime numbers
    isprime[0] = isprime[1] = False

    # prime[] is used to store all prime number less than N
    prime = []

    """SPF[] that stores the smallest prime factor of number
    [for ex : smallest prime factor of '8' and '16' is '2' so we put SPF[8] = 2 ,
     SPF[16] = 2 ]
    """
    SPF = [None] * N

    # Step 1
    for i in range(2, N):

        # If isPrime[i] == True then i is
        # prime number
        if isprime[i] == True:
            # put i into the list prime[]
            prime.append(i)

            # A prime number is its own smallest
            # prime factor
            SPF[i] = i
            
    #Step 2
        """ Mark all multiples of i*prime[j] which are not prime  as False by making Prime[i * prime[j]] = false 
            and put the smallest prime factor of i*Prime[j] as prime[j]
            [ for example: let i = 3 , j = 0 ,prime[j] = 2 [ i*prime[j] = 6 ]
            so smallest prime factor of '6' is '2' that is prime[j] ] this loop run only one time for 
            number which are not prime
        """
        j = 0
        while (prime[j] <= SPF[i]) and (j < len(prime) and (i * prime[j] < N):
            isprime[i * prime[j]] = False

            # put smallest prime factor of i*prime[j]
            SPF[i * prime[j]] = prime[j]

            j += 1
    return prime


if __name__ == "__main__":

    n = int(input("Enter the number:"))

    prime = modified_seive(n)

    # print all prime number less then N
    i = 0
    for p in prime:
        print(p, end=" ")
        i += 1

Enter the number:100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
Process finished with exit code 0