Modified Sieve of Eratosthenes in O(n) Time complexity Explained with Python code

Our task is to find all the prime numbers that are less than n in Linear Time.

We use Sieve of Eratosthenes to find the prime numbers till n.
But the time complexity is O(N log (log N)).
Here our desired time complexity is O(N). Hence a modified version of the Sieve of Eratosthenes is to be used.

Modified Sieve of Eratosthenes algorithm

 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.

Python code implementation

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

Output

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

Proof of correctness:

We need to prove that the algorithm sets all values $SPF[]$ correctly, and that every value will be set exactly once. Hence, the algorithm will have linear runtime, since all the remaining actions of the algorithm, obviously, work for O(n).

Notice that every number i has exactly one representation in form:

$i=SPF[i]*x$,

where $SPF[i]$ is the minimal prime factor of i, and the number x doesn't have any prime factors less than $SPF[i]$, i.e.

$SPF[i] \le SPF[x]$.

Now, let's compare this with the actions of our algorithm: in fact, for every $x$ it goes through all prime numbers it could be multiplied by, i.e. all prime numbers up to $SPF[i]$ inclusive, in order to get the numbers in the form given above.

Hence, the algorithm will go through every composite number exactly once, setting the correct values $SPF[]$ there

References

• David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]
• CP Algorithms - Sieve of Eratosthenes Having Linear Time Complexity