Having a try at computing the sieve of Eratosthenes

Question

I'm an absolute novice to python but I am trying to compute something that should act like the sieve of Eratosthenes.

I'm going to start easy and just create a set with all integers from 2 up to 100. Let's call that set S.

I then want to create a set of all integers n such that 2n is contained in that set, let's call it P1. In other words, a set of the integers 2, 4, 6, 8 etc.

I want to then do the same thing but with P2 = 3n and then P3 = 5n.

In the end I want to return all integers of my set S but disregard the integers in P1, P2 and P3.

How would I go on about doing this?

My try:

  numbers=set(range(2,100))

but I'm stuck on creating the other sets and disregarding them!

Thanks.

My idea so far:

def sieve(n):
    S = set(range(2, 100))
    P1 = set(range(0, 100, 2))
    P2 = set(range(0, 100, 3))
    P3 = set(range(0, 100, 5))
    P5 = set(range(0, 100, 7))
    return S-P1-P2-P3-P5
print (sieve(100))

Try `range(2, 100, 2)`, `range(3, 100, 3)`, etc. The third parameter is the step. — tobias_k, Jan 21 '14 at 20:31
Ok cool, what exactly does range(2,100,2) mean? I realize that (2,100) means from 2 to 100...What is the extra ,2 for? — user3200098, Jan 21 '14 at 20:43
@user3200098 Try typing `help(range)` into your interpreter. This gives you the following information: "Returns a virtual sequence of numbers from start to stop by step.". Which is to say, it steps by 2 at a time, so that you get the numbers 2, 4, 6, ..., 96, 98. — senshin, Jan 21 '14 at 20:45
Hey guys, if you could take a look at the code I posted and tell me why the sequence goes haywire when I try to remove the 7 step set, that would be great. — user3200098, Jan 21 '14 at 21:02
The problem is that you are using a `set`, which is not ordered. I do not know why the numbers _are_ ordered until you remove `P5`, but that's the "natural" way for a `set` to look. If you want them ordered, use `sorted(sieve(100))`, which will create an ordered `list` from the `set`. — tobias_k, Jan 21 '14 at 21:09
Where can I post the code? I am still having a problem. Using sorted(sieve(100)) prints nothing. — user3200098, Jan 21 '14 at 21:12
Did you try `print(sorted(sieve(100)))`? Sorry if that was not clear... — tobias_k, Jan 21 '14 at 21:15
Sorry, one more question and my naive sieve should work. I'm trying to collect the elements that got left out but were still primes (2,3,5,7)...How do I create a set of integers like that? I tried set(2,3,5,7) but that doesn't seem to work. — user3200098, Jan 21 '14 at 21:20
The easiest way would be to not have them in the set you subtract. Instead of `range(0,100,x)` use `range(x*x,100,x)`. Otherwise you could add back in `set([2,3,5,7])`. P.S. have a look at http://stackoverflow.com/questions/9301781/fastest-in-term-of-space-way-to-find-prime-numbers-with-python — Mark Ransom, Jan 21 '14 at 21:27

score 0 · Answer 1 · answered Jan 21 '14 at 20:44

0

Here a snippet with answering your specific question (not the whole sieve):

S = set(range(2, 101)) #numbers 2 to 100
P1 = set(range(2, 101, 2)) #2n
P2 = set(range(3, 101, 3)) #3n
P3 = set(range(5, 101, 5)) #5n
print ('S = ', S)
print ('P1 = ', P1)
print ('P2 = ', P2)
print ('P3 = ', P3)
S = S - P1 - P2 - P3 #Here comes the "discarding"
print ('S = ', S)

Obviously you won't want to hardcode your Px sets, and you will want to identify the next primer by looking at the next unsieved number.

answered Jan 21 '14 at 20:44

Hyperboreus

31,997
9
47
87

My code works fine until I do a P4 = set(range(0, 100, 7)) then the whole sequence is screwed. How come? Isn't it just supposed to remove 7, 14, 21 etc? – user3200098 Jan 21 '14 at 20:59
It should be range(7, 100, 7) and not range(0, 100, 7). – Hyperboreus Jan 22 '14 at 06:17

score 0 · Answer 2 · answered Jan 21 '14 at 20:44

The range function accepts a third parameter: The step. For example, range(2, 10, 3) is [2, 5, 8]. You can use this to build sets of multiples of some number, e.g. range(3, 100, 3) for the multiples of 3 smaller than 100, including 3 itself.

Combine those with the - operator on sets to build a first, naive version of the sieve:

p = set(range(2, 100))
for i in range(2, 10):
    p = p - set(range(i, 100, i))
print sorted(p)

However, this will also remove the tested is themselved, thus lacking the first few primes:

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, ...]

Fixing this algorithm is left as an excercise to the reader. ;-)

score 0 · Answer 3 · answered Jan 22 '14 at 19:37

might try this:

def filter_primes(alist, newlist):
    for x in alist[1:]:
        if x%alist[0] != 0:
            newlist.append(x)
    return newlist

alist = range(2, 100)
sieve_list = []
primes = [2]

while len(alist) > 1:
    a = filter_primes(alist, sieve_list)
    primes.append(a[0])
    alist = sieve_list
    sieve_list = []

print primes

Out[1]:  [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]

Should work for any number, not just 100.

Having a try at computing the sieve of Eratosthenes

3 Answers3