Advertisement
jk464

Sieve of Eranthoses

Mar 7th, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.16 KB | None | 0 0
  1. import datetime
  2.  
  3. #sieve of eranthoses
  4.  
  5. #function to create intial sieve
  6. def numList(upTo):
  7.     primes = []
  8.     for i in range(upTo):
  9.         primes.append(True)
  10.     return primes
  11.  
  12. #function to perform the sieving
  13. def primeCalc(primes):
  14.     primes[1] = False #1 is not prime
  15.     prime_counter = 0 #intializing prime counter
  16.  
  17.     for i in range(len(primes)): #for loop to go through the array of numbers to test
  18.         if i==0: #skip 0, count array from 1
  19.             print("")
  20.         else:
  21.             if primes[i]: #if the ith element is true then this is a prime
  22.                 prime_counter = prime_counter + 1 #inc prime counter
  23.  
  24.                 #remove multiples of this prime as possible primes
  25.                 counter = 2 * i
  26.                 # print(counter)
  27.                 while counter <= len(primes) - 1:
  28.                     primes[counter] = False
  29.                     counter = counter + i
  30.                     # print(counter)
  31.  
  32.     print(prime_counter)
  33.  
  34. startTime=datetime.datetime.now()
  35.  
  36. primeCalc(numList(1000000))
  37.  
  38. endTime=datetime.datetime.now()
  39.  
  40. print("------------------------")
  41. print("Time to Commute: "+str(endTime-startTime))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement