Sieve of Eratosthenes


/ Published in: Python
Save to your folder(s)

Function (algorithm) that returns all prime numbers up to n.


Copy this code and paste it in your HTML
  1. def E_sieve(n):
  2. A=[]
  3. for p in range(2, n+1): # fils the list with numbers from 2 up to n
  4. A.append(p)
  5. for p in range(2, int(floor(n)-1)):
  6. if A[p]!=0: # cheks if p had been eliminated in any of the previous passess
  7. j=p*p
  8. while j<=n-2:
  9. A[j]=0 # marks element as eliminated
  10. j+=p
  11. # copying the remaining elements from list A into list L
  12. i=0
  13. L=[]
  14. for p in range(2, n-1):
  15. if A[p]!=0:
  16. L.append(p)
  17. i+=1
  18. return L

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.