def primes(n):
s=[1,]+range(4,n+1,2)+range(6,n+1,3)+range(10,n+1,5)+range(14,n+1,7)
for x in (2,3,5,7):
s+=range(x*2,n+1,x)
l=range(1,n+1)
s.sort()
primes=list(set(l)-set(s))
return primes
Refactorings
No refactoring yet !
bob
December 18, 2009, December 18, 2009 01:23, permalink
No rating.
Login to rate!
What about multiples of things that are bigger than 2, 3, 5, or 7? For example, 121?
Eli
December 26, 2009, December 26, 2009 06:24, permalink
No rating.
Login to rate!
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# Maps composites to primes witnessing their compositeness.
# This is memory efficient, as the sieve is not "run forward"
# indefinitely, but only as long as required by the current
# number being tested.
#
D = {}
# The running integer that's checked for primeness
q = 2
while 1:
if q not in D:
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations
#
yield q
D[q * q] = [q]
else:
# q is composite. D[q] is the list of primes that
# divide it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiples of its witnesses to prepare for larger
# numbers
#
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
Eli
December 26, 2009, December 26, 2009 06:33, permalink
No rating.
Login to rate!
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# Maps composites to primes witnessing their compositeness.
# This is memory efficient, as the sieve is not "run forward"
# indefinitely, but only as long as required by the current
# number being tested.
#
D = {}
# The running integer that's checked for primeness
q = 2
while 1:
if q not in D:
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations
#
yield q
D[q * q] = [q]
else:
# q is composite. D[q] is the list of primes that
# divide it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiples of its witnesses to prepare for larger
# numbers
#
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
Nick
January 28, 2010, January 28, 2010 19:33, permalink
No rating.
Login to rate!
This is what I came up with. Mine obviously takes an int to specify an upper bound.
# This function returns a list of the primes
# between 2 and n inclusively. It is given
# an integer n and prints the list.
def sieve(n):
i = 2 # initialize a counter to create the list
theList = [] # initialize both lists as empty
theNums = []
while(i < n+1): # create two lists from 2 to n inclusively
theList.append(i)
theNums.append(i)
i = i + 1
for num in theList: # for every number in theList, we multiply it by
# (2, 3, 4, 5, ...n) by using theNums list"
for x in theNums:
if(theList.count(num * x) != 0): # to prevent errors, we check to ensure
# the num we want to remove is in the list
theList.remove(num * x) # if it is, we remove it
x = x + 1 # increment our counters
num = num + 1
print(theList) # print the completed list of primes when done
I've purposely avoided looking at how other people have done this one so that I can take a whack at it myself. Here's what I came up with.