# Better Sieve

## Akshay Bist 3rd of April 2012

```#!/usr/bin/env python

# Sieve of Eratosthenes - to find all the prime numbers in range 1 to n
# http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
# Optimized by only putting in 2, 3 & numbers of the form 6n+/-1 in the initial list.

def better_sieve(n):
primes = []
numbers = []
if 2<=n:
primes.append(2)
if 3<=n:
primes.append(3)
for i in range(1, n/6 +1):
numbers.append(6*i-1)
numbers.append(6*i+1)
while numbers:
primes.append(numbers.pop(0))
for e in numbers:
if not e%primes[-1]:
numbers.pop(numbers.index(e))
return primes

def is_prime(n):
prime_list = better_sieve(n)
if n in prime_list:
return True
return False```
253
Views
0
Comments
0
Downloads
Comments
Only Code Pad members can post comments!

Want to join Code Pad Request An Invite
No Comments Posted

Suppo - Create, Customize & Host
Your App Support Page at Suppo

### Snippet Details

• Status: Public
• Description: Optimized the Sieve of Eratosthenes a little by only putting in 2, 3 & numbers of the form 6n+/-1 in the initial list
• Saved by: Akshay Bist
• Type: Python
• Date: 3rd April 2012
• Characters: 693
• Views: 253
• Likes:
• Downloads:
Keyboard Shortcuts

DDownload

TTweet

FFull View

Next Snippet

Previous Snippet