gotchapythonMinor

Naive prime finder, unexpected behavior in Python

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

naivebehaviorfinderunexpectedpythonprime

Problem

I have verified that both of my following functions successfully find prime numbers. I was pretty sure the function called is_prime_new would be faster than is_prime_old; however, after benchmarking (mainly consisting of generating huge lists of primes), I found this to be significantly false and I'm wondering why this may be.

I had two main reasons for thinking that is_prime_new would be a better algorithm than its counterpart:

-
is_prime_new does more checks for non-primailty early, thus eliminating numbers before iteration

-
It iterates in steps of 6, whereas its counterpart iterates in steps of 2, both to the same value sqrt(n)+1

Could anyone explain to me why the newer function is less optimized, and possibly debunk my above assumptions? Thank you.

def is_prime_new(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqr = math.sqrt(n)
    if sqr == int(sqr): return False

    i = 1
    while i*6 < sqr+1:
        if n % (i*6-1) == 0 or n % (i*6+1) == 0: return False
        i += 1

    return True

def is_prime_old(n):
    if n < 2: return False
    if n == 2: return True
    if n%2 == 0: return False

    for i in xrange(3, int(math.sqrt(n)+1), 2):
        if not n%i: return False

    return True

Solution

Duncan's explanation is incorrect. This isn't my best piece of writing - bear with me.

First lets deal with

n 

The time spent on this part of the function is very insignificant compared to that spent in the rest of the function.



Next

n%2 == 0 or n%3 == 0

Again n%2 == 0 is in the old definition also.

n%3 == 0 is the first check in old's for loop




The time spent on this part of the function is also insignificant compared to that spent in the rest of the function.



I could've clubbed this with the previous section but didn't for the following reason:

These checks work on 4 out of every 6 input numbers. And 4 > 6-4. But is that the way to look at it? If say they'd worked on 3/6 [As in the case of

old

] are these checks useless? If say they'd worked on 2/6 should they be avoided? No.

By doing one(or two) comparison(s) on 6 inputs, they stop 2 from reaching the work horse of the code - the loop - that does most of the work. That's not to be avoided!

Also, by imposing additional constraints on the input that reaches the loop, the loop itself has been made faster! Knowing that no multiple of 3 enters the loop, you don't test divisibility of n by any other multiple of 3. Don't forget your main idea behind moving from

old to new

!

Faster loop + lesser numbers reaching loop should make

new faster than old

.

How much faster exactly?

- 
I mentioned "lesser numbers reaching loop" being good only as a general guideline. It doesn't help much here because : In

old 3,5,7,9... enter the loop, and in new 5,7,11,13... enter the loop. But in old

 3,9... get stopped at the first check of the for loop. So only faster loop is important.

-

new's loop jumps in steps of 6 but old's jumps in steps of 2. So is new 3 times faster than old? No. At every step new does 3 comparisons - one for the while loop condition and two inside the loop. old does 2 - one at for loop condition and one inside the loop. So, new is (6/3) * (2/2) = 2 times faster than old

.

So far I've only been explaining why

new

 should be faster. Finally I'll address your question of why this isn't observed:

for loops are much faster than while loops. python doesn't know how i is going to change inside while. So the while loop's condition check is like any other comparison. On the other hand for loop's condition check is highly optimised. Henceforth lets assume that for

 loop's condition check doesn't count as a comparison.

Then

old's time/new

's time will be

6/3 * 2/2 = 2 if both use while

6/2 * 1/2 = 1.5 if both use for

6/2 * 2/2 = 3 if old used while and new used for

6/3 * 1/2 = 1 if old used for and new used while




That still means that

old and new

 should be (at least approximately) equally fast. This is where I was stumped. I had to resort to experimenting to figure this out. The reasons for this not occurring, as it turns out, are

All the unnecessary arithmetic (*6) in the while loop

while i*6

Note that the ratios provided are from rough calculations and far from being accurate - there are so many more things to consider. One major assumption is that time spent in the loops is much larger than time spent at base case checks - not true if all your input are multiples of 2.

To summarise, the reasons for new being slower, despite being expected to be faster, are:

Usage of while instead of for (this is not as important as the other two)

Unnecessary arithmetic inside while

Usage of float comparison instead of int comparison in while condition check.

The code given below illustrates some of the points made here.

```
import math, timeit

def is_prime_new_slowest(n):
if n half:
return [2] + filter(None, numbers)

i = sundaram3(10**6)[-1]

print "Input: largest prime less than 10^6, No. of runs: 25000"
print "new slowest:", timeit.timeit('is_prime_new_slowest(i)', setup="from __main__ import is_prime_new_slowest, i; import math", number=25000)
print "new slow:", timeit.timeit('is_prime_new_slow(i)', setup="from __main__ import is_prime_new_slow, i; import math", number=25000)
print "new fast:", timeit.timeit('is_prime_new_fast(i)', setup="from __main__ import is_prime_new_fast, i; import math", number=25000)
print "old slow:", timeit.timeit('is_prime_old_slow(i)', setup="from __main__ import is_prime_old_slow, i; import math", number=25000)
print "old fast:", timeit.timeit('is_prime_old_fast(i)', setup="from __main__ import is_prime_old_fast, i; import math", number=25000)

print "\nInput: range(1000000), No. of runs = 1"
print "new slowest:", timeit.timeit('for i in xrange(1000000): is_prime_new_slowest(i)', setup="from __main__ import is_prime_new_slowest; import math", number=1)
print "new slow:", timeit.timeit('for i in xrange(1000000): is_prime_new_slow(i)', setup="from __main__ import is_prime_new_slow; import math", number=1)
print "new fast:", timeit.timeit('for i in xrange(1000000): is_prime_new_fast(i)', s

Code Snippets

import math, timeit

def is_prime_new_slowest(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqr = math.sqrt(n) #This is insignificant as it is outside the loop
    if sqr == int(sqr): return False
    sqrtp1 = sqr + 1 #Note that sqrtp1 is a float
    i = 1
    while i*6 < sqrtp1: # Comparison of floats adds some time
        if n % (i*6-1) == 0 or n % (i*6+1) == 0: return False #Unnecessary arithmetic
        i += 1
    return True

def is_prime_new_slow(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqrtp1 = int(math.sqrt(n) + 1)
    i = 6
    while i < sqrtp1:
        if n % (i-1) == 0 or n % (i+1) == 0: return False
        i += 6
    return True

def is_prime_new_fast(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqrtp1 = int(math.sqrt(n)+1)
    for i in xrange(6, sqrtp1, 6):
        if n % (i-1) == 0 or n % (i+1) == 0: return False
    return True

def is_prime_old_slow(n):
    if n < 2: return False
    if n == 2: return True
    if n%2 == 0: return False
    sqrtp1 = int(math.sqrt(n) + 1)
    i = 3
    while i < sqrtp1:
        if not n%i: return False
        i += 2
    return True

def is_prime_old_fast(n):
    if n < 2: return False
    if n == 2: return True
    if n%2 == 0: return False
    sqrtp1 = int(math.sqrt(n)+1)
    for i in xrange(3, sqrtp1, 2):
        if not n%i: return False
    return True

def sundaram3(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)//2
    initial = 4
    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)
        if initial > half:
            return [2] + filter(None, numbers)

i = sundaram3(10**6)[-1]

print "Input: largest prime less than 10^6, No. of runs: 25000"
print "new slowest:", timeit.timeit('is_prime_new_slowest(i)', setup="from __main__ import is_prime_new_slowest, i; import math", number=25000)
print "new slow:", timeit.timeit('is_prime_new_slow(i)', setup="from __main__ import is_prime_new_slow, i; import math", number=25000)
print "new fast:", timeit.timeit('is_prime_new_fast(i)', setup="from __main__ import is_prime_new_fast, i; import math", number=25000)
print "old slow:", timeit.timeit('is_prime_old_slow(i)', setup="from __main__ import is_prime_old_slow, i; import math", number=25000)
print "old fast:", timeit.timeit('is_prime_old_fast(i)', setup="from __main__ import is_prime_old_fast, i; import math", number=25000)

print "\nInput: range(1000000), No. of runs = 1"
print "new slowest:", timeit.timeit('for i in xrange(1000000): is_prime_new_slowest(i)', setup="from __main__ import is_prime_new_slowest; import math", number=1)
print "new slow:", timeit.timeit('for i in xrange(1000000): is_prime_new_slow(i)', setup="from __main__ import is_prime_new_slow; import math", number=1)
print

Input: largest prime less than 10^6, No. of runs = 25000
new slowest: 7.37190294266
new slow: 4.19636297226
new fast: 3.49502682686
old slow: 6.08556985855
old fast: 4.03657603264

Input: range(1000000), No. of runs = 1
new slowest: 21.5607540607
new slow: 13.8396618366
new fast: 12.3734707832
old slow: 20.0376861095
old fast: 14.1358599663

Context

StackExchange Code Review Q#19278, answer score: 3

Revisions (0)

No revisions yet.