Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. Here’s a Python Implementation of sieve of Eratosthenes.

"""
Created on Wed Sep 25 14:07:59 2013
 
@author: sukhbinder
 
Python Implementation of sieve of Eratosthenes
 
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves,
is a simple, ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e. not prime) the multiples of 
each prime, starting with the multiples of 2.
 
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
 
"""
 
import numpy as np
 
def SOE(n):
    is_p = np.ones((n,),dtype=bool)
    is_p[:2]=0
    nmax = np.int(np.sqrt(n))
    #print nmax,range(2,nmax)
    for j in range(2,nmax+1):
        is_p[2*j::j]=False
        #print is_p.nonzero()
    #print is_p
    return is_p.nonzero()

Prime Seive

So what are the prime weeks of the year?
print SOE(53)

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

What are the prime days in the month?
print SOE(32)

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

What are the prime days in the year?
print SOE(366)

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359]

Advertisements

4 thoughts on “Sieve of Eratosthenes

  1. When I originally commented I clicked the -Notify me when new feedback are added- checkbox and now each time a comment is added I get 4 emails with the same comment. Is there any method you’ll be able to remove me from that service? Thanks!

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s