lundi 25 juillet 2016

Sieve of Eratosthenes returning incorrect answers

I'm a beginner trying to create a function to determine whether or not a value is prime or not.

def isPrime(number):
    marked = [] ## create empty list
    for i in xrange(2, number+1):
        if i not in marked: ## begin loop to remove multiples of i in list
            for j in xrange(i * i, number + 1, i):
                marked.append(j)
            if i == number: ## I'm assuming that if 
            ##the program made it here, i is not in marked.

print isPrime(7)
>>> True
print isPrime(10)
>>> None ## This should be False...ok so I tried to tinkering here.

So my attempt to fix that was to edit the last conditional to:

if i == number:
    return True
else: ## Begin new line of code to correct for false positive
    return False

This extra line messes up everything though because it now shows:

isPrime(7)
>>> False

...which is clearly wrong.

I'm struggling with the intuition here - I've been playing with using an AND function after:

if i not in marked:

...that didn't yield the correct answers either.

I'm struggling to figure out what the best manner of fixing this code would be with the goal of determining if the number passed in the function is prime or not.

Thanks for your help!

Aucun commentaire:

Enregistrer un commentaire