Advanced Search

Sieve of Eratosthenes

/ Published in: Python
Save to your folder(s)
Function (algorithm) that returns all prime numbers up to n.

Expand | Embed | Plain Text

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.