iframe-proxy | Sunbelt Computer Software

Repository navigation

# 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)