Created
February 21, 2011 07:04
-
-
Save sj26/836755 to your computer and use it in GitHub Desktop.
The fastest way I could implement Erastothenes prime number sieve in Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys, collections | |
cases = int(sys.stdin.readline().strip()) | |
for case in range(1, cases + 1): | |
candidate_min, candidate_max = map(int, sys.stdin.readline().strip().split()) | |
# Python is good at sparse dictionaries, so use a bubbling | |
# Sieve of Erastothenes to be memory efficient and fairly | |
# computationally efficient | |
composites = collections.defaultdict(list) | |
for candidate in range(2, candidate_max + 1): | |
if candidate not in composites: | |
# This candidate is prime! | |
# Print it if we should | |
if candidate >= candidate_min: | |
print(candidate) | |
# Find the first composite of this prime. | |
composites[candidate * candidate] = [candidate] | |
else: | |
# This candidate is a composite. | |
# Find the next multiple of each prime which found this composite. | |
for prime in composites[candidate]: | |
composites[prime + candidate].append(prime) | |
# We don't care about this candidate any more. | |
del composites[candidate] | |
print() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
... but it's still not fast enough. :-(