P67_SieveOfEratosthenes.py

# Auhtor: OMKAR PATHAK

# Sieve of Eratosthenes is one of the efficient algorithms to find all the prime numbers upto n, where n can be
# upto 10 million. This algorithm is very efficient and fast and hence is preferred by many competitive programmers.

# Algo:
# 1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
# 2. Initially, let p equal 2, the first prime number.
# 3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list.
#    These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
# 4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise,
#    let p now equal this number (which is the next prime), and repeat from step 3.
# When the algorithm terminates, all the numbers in the list that are not marked are prime.

def SieveOfEratosthenes(n):
    primes = [True] * (n + 1)
    p = 2                   # because p is the smallest prime

    while(p * p <= n):
        # if p is not marked as False, this it is a prime
        if(primes[p]) == True:
            # mark all the multiples of number as False
            for i in range(p * 2, n + 1, p):
                primes[i] = False

        p += 1
        
    # printing all primes
    for i in range(2, n):
        if primes[i]:
            print(i)

if __name__ == '__main__':
    SieveOfEratosthenes(1000)