Skip to content

Instantly share code, notes, and snippets.

@gamesbrainiac
Created June 14, 2013 21:22
Show Gist options
  • Save gamesbrainiac/5785397 to your computer and use it in GitHub Desktop.
Save gamesbrainiac/5785397 to your computer and use it in GitHub Desktop.
Now, this is a beautiful algorithm.
import time
__author__ = 'Nafiul Islam'
__title__ = 'Summation of primes'
# Very slow implementation for some reason
# Modelled after the sieve of Eratosthenes
def main(limit=1000):
# Because xrange() goes to limit-1
limitn = limit+1
# Creates a list, False means the index is a prime.
not_prime = [False] * limitn
# Creates a list to append indexes that are primes
# primes = []
# total for total sum
total = 0
# Looping over all the values up to limitn from 2
for i in xrange(2, limitn):
# If index is a prime number, then skip all else
if not_prime[i]:
continue
# If index is not a prime number
# Change all multiples of that number,
# starting from its double to True,
for f in xrange(i*2, limitn, i):
# meaning making them not primes
not_prime[f] = True
# primes.append(i)
total += i
# Prints total
print '== Total =='
print total
if __name__ == "__main__":
start_time = time.time()
main(1000000,)
print time.time() - start_time, "seconds"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment