# 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()

```

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]

## 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

• hopefully approving this will solve your problem.. definitely a wordpress issue……

Like

2. My relatives always say that I am wasting my time here at net,
but I know I am getting familiarity all the time by reading such nice articles.

Like