sieve of eratosthenes python

Solutions on MaxInterview for sieve of eratosthenes python by the best coders in the world

showing results for - "sieve of eratosthenes python"
Esteban
11 Nov 2016
1#The other code in Grepper(By Disgusted Donkey) is in python2
2#this one is python3
3
4def SieveOfEratosthenes(n): 
5      
6    # Create a boolean array "prime[0..n]" and initialize 
7    # all entries it as true. A value in prime[i] will 
8    # finally be false if i is Not a prime, else true. 
9    prime = [True for i in range(n + 1)] 
10    p = 2
11    while (p * p <= n): 
12          
13        # If prime[p] is not changed, then it is a prime 
14        if (prime[p] == True): 
15              
16            # Update all multiples of p 
17            for i in range(p * 2, n + 1, p): 
18                prime[i] = False
19        p += 1
20    prime[0]= False
21    prime[1]= False
22    # put all prime numbers in a list
23    r = []
24    for p in range(n + 1): 
25        if prime[p]: 
26            r.append(p) 
27    #return the list        
28    return r
29  
30# driver program 
31if __name__=='__main__': 
32    n = 50
33    print ("Following are the prime numbers smaller") 
34    print ("than or equal to", n)
35    print(SieveOfEratosthenes(n))