CODEWITHSUNDEEP
pythonalgorithmprimes
Just some guy
Just some guy

Reputation: 1959

Python - Why doesn't this prime number checking algorithm work?

I have this python code that I wrote:

from math import *

limit = 100000
primes = [2]

for i in range(3, limit+1, 2):
    is_prime = True
    for j in range(3, floor(sqrt(i)), 2):
        if i % j == 0:
            is_prime = False
            break
    if is_prime: primes.append(i)

print(len(primes))

It says there are 9676 primes less than 100 000, when it should be 9592. It gives the correct answer if I the replace floor(sqrt(i)) with just i, but then it's terribly slow. Why doesn't my algorithm work?

Upvotes: 0

Views: 116

Answers (2)

glibdud
glibdud

Reputation: 7850

Take, for example i == 9. The following range:

for j in range(3, floor(sqrt(i)), 2):

Evaluates to:

for j in range(3, 3, 2):

...which is an empty list, preventing non-prime 9 from being ruled out. You need to go one higher to ensure that the root of square numbers is considered:

for j in range(3, floor(sqrt(i)) + 1, 2):

Upvotes: 7

Thomas Kimber
Thomas Kimber

Reputation: 11077

You're including primes that are squares of other primes - I changed the sqrt range definition in your code to get:

from math import *

limit = 100000

primes = [2]

for i in range(3, limit+1, 2):
    is_prime = True
    for j in range(3, floor(sqrt(i))+1, 2):
        if i % j == 0:
            is_prime = False
            break
    if is_prime: primes.append(i)

print(len(primes))

resulting in 9592 primes found

Upvotes: 4

Related Questions