Posted By

Kartoffel on 06/29/08


Tagged

numbers prime eratostenes sieve


Versions (?)

Sieve of Eratostenes


 / Published in: Python
 

An (probably inefficient) implementation of the Sieve of Eratostenes. The function returns a list containing all the prime numbers between 0 and the number passed to it.

  1. # -*- coding: utf-8 -*-
  2.  
  3. def eratostenes(num, print_nums=False):
  4. if num < 3:
  5. raise Exception, 'Number is too small'
  6. full_nums = range(num)[1:] + [num]
  7. primes = [False] + [True]*(num - 1)
  8. for i in range(num):
  9. if primes[i]:
  10. if print_nums:
  11. print full_nums[i]
  12. inc = full_nums[i]
  13. cursor = i + inc
  14. if cursor > num:
  15. break
  16. while cursor < num:
  17. primes[cursor] = False
  18. cursor += inc
  19. return [full_nums[j] for j in range(num) if primes[j]]

Report this snippet  

You need to login to post a comment.