CODEWITHSUNDEEP
pythonfor-loopdictionaryprimes
Benster
Benster

Reputation: 23

Python: Primes using Sieve of Eratosthenes and dictionary

Hey I was trying to write some code to get primes using the Sieve of Eratosthenes. Employing a dictionary with numbers for the range to check I set the value to True when I checked it is not a prime. But something is not working correctly and instead of skipping to the next number if the value is True (= already checked) it tests it again. What am I doing wrong?

max=12
checked={}
primes =[]
numbers=[]

for i in xrange(2,max):
    numbers.append(i)
    checked[i] = False      

for i in numbers:
    if checked[i] == True:
        continue 
        #if the number was already checked continue with next
    else:
        primes.append(i) 
        #lowest unchecked number is always a prime
        checked[i] = True 
        for x in numbers:
            if x%i==0:
            #checking off all the multiples of the prime
                checked[x]=True
                print x

print primes

Now I get this Output

2
4
6
8
10
3
6
9
5
10
7
11
[2, 3, 5, 7, 11]

Clearly the 6 and 10 are checked twice instead of skipped.

Upvotes: 0

Views: 396

Answers (2)

Benster
Benster

Reputation: 23

Here is the correct code:

max=12
checked={}
primes =[]
numbers=[]

for i in xrange(2,max):
    numbers.append(i)
    checked[i] = False      

for i in numbers:
    if checked[i] == True:
        continue 
        #if the number was already checked continue with next
    else:
        primes.append(i) 
        #lowest unchecked number is always a prime
        checked[i] = True 
        for x in numbers:
            if x%i==0 and checked[x]==False:
            #checking off all the multiples of the prime
                checked[x]=True
                print x

print primes

Upvotes: 0

grasshopper
grasshopper

Reputation: 4068

It works for me. Just replace the sixth line with:

for i in xrange(2,max+1):

The +1 is because without it the algorithm does not check the max number the user gave.

Also:

numbers = range(2,max+1)

It doesnt really matter if you use the generator xrange, but then save all the numbers in a list anyway, so why not do it in one line.

To address the OP's clarification in the comments:

It checks 6 and 10 twice because 6 is a multiple of the primes 2 and 3 and 10 is a multiple of the primes 5 and 2. If you dont want it to do that add:

if x%i==0 and checked[x] is not True:

although it wont save you anything performance-wise..

Upvotes: 1

Related Questions