Skip to content

Instantly share code, notes, and snippets.

@viveksyngh
Created August 2, 2015 12:37
Show Gist options
  • Save viveksyngh/52aaf9b6297745138dc8 to your computer and use it in GitHub Desktop.
Save viveksyngh/52aaf9b6297745138dc8 to your computer and use it in GitHub Desktop.
Implementation of sieve of eratosthenes
__author__ = 'Vivek'
#Implementation of Sieve of eratosthenes , It returns an array containing all prime numbers less than A ( Including A)
def sieve(A):
"""
:param: An integer A
:return: An array of prime number less than equal to A
"""
L = [1] * (A + 1)
L[0] = 0
L[1] = 0
for i in range(2, int(A**0.5) + 1) :
if L[i] == 1 :
j = 2
while i * j <= A :
L[i * j] = 0
j = j + 1
res = []
for i in range(len(L)) :
if L[i] == 1:
res.append(i)
return res
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment