Advanced Search

Sieve of Eratostenes

/ Published in: Python
Save to your folder(s)
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.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  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


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.