Take the 2-minute tour ×

I'm trying to do a simple primality test in Python.

Accoding to Wikipedia, a primality test is the following:

Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime.

I started with ruling out the even numbers - with the exception of 2 - as candidates to prime

def prime_candidates(x):
    odd = range(1, x, 2)
    odd.insert(0, 2)
    return odd

Then writing a function to check for primes, according to the rules above.

def isprime(x):
    for i in range(2, x-1):
            if x % i == 0:
                    return False
                    return True

And this is the main function, which iterates over a list of 8000 prime candidates and tests their primality

def main():
    end = 8000
    candidates = prime_candidates(end)
    for i in candidates:
            if isprime(i) and i < end:
                    print 'prime found ' + str(i)

The problem is that the isprime function returns True for numbers that aren't primes.

share|improve this question
candidates could just be [2] + range(3, end, 2). I don't know why you include zero. And you don't need to test and i < end; that's guaranteed by range(..., end, ...). –  Marcelo Cantos Nov 5 '11 at 9:44
Note that you don't have to check up to n-1. It's enough to check up to sqrt(n) as anything higher than that will surely not divide it or has already been checked by a number lower than the square root. –  Paul Manta Nov 5 '11 at 9:45
Also note that all canidate generation approaches mentioned make an unnecessary copy. xs = range(1, x, 2); xs[0] = 2 makes not copies, and with xrange (plain range in 3.x) and itertools.chain one can even avoid storing more than one canidate at a time. –  delnan Nov 5 '11 at 9:48
@MarceloCantos candidates doesn't include zero, it starts from 1, I'm just inserting 2 at the beginning. –  Mahmoud Hossam Nov 5 '11 at 9:52
@PaulManta range doesn't accept float, which sqrt(n) returns, and casting to int messes up the result due to rounding error. –  Mahmoud Hossam Nov 5 '11 at 9:53
show 5 more comments

4 Answers

up vote 7 down vote accepted

In brief, your isprime(x) checks whether the number is odd, exiting right after if x % 2 == 0.

Try a small change so that you would actually iterate:

def isprime(x):
    for i in range(2, x-1):
        if x % i == 0:
            return False
        return True

Note that else: is now part of the for loop rather than if statement.

share|improve this answer
While this solution is completely fine, the solution below with the "while" loop over d * d <= n is going to be markedly faster. This is not the optimal solution, IMHO. –  Mike Williamson Dec 6 '12 at 1:00
Given that it's a homework, I did not assume that the performance mattered. The question itself was "what's wrong," there were no question on how would one make it better. –  alf Dec 6 '12 at 16:58
apologies... didn't mean to criticize your solution. You're correct. I was just wondering why the community was voting this solution over the one that only goes up to sqrt(n). –  Mike Williamson Dec 13 '12 at 17:55
Any reason to put the second return in an else block? The for/else construct is rather uncommon, and unneeded here given that the loop does not contain a break statement. –  Clément Nov 9 '13 at 18:42
That's 2 years ago. I guess the reason was to keep the change to the minimum. –  alf Nov 10 '13 at 19:14
add comment

Have a look at the Miller–Rabin primality test if a probabilistic algorithm will suffice. You could also prove a number to be prime, with for instance Elliptic Curve Primality Proving (ECPP), but it takes more effort.

A simple trial division algorithm is the following

def prime(a):
     return not (a < 2 or any(a % x == 0 for x in range(2, int(a ** 0.5) + 1)))
share|improve this answer
The problem says I have to use trial division. –  Mahmoud Hossam Nov 5 '11 at 9:42
This is homework. The exercise is a means to teach programming! –  David Heffernan Nov 5 '11 at 9:43
@David: I don't understand your point. Clearly Mahmoud gave an effort... he supplied his entire code. Asking this community is like asking the TA for help, right? I completely agree we should not simply provide answers, but providing help in debugging homework seems wonderfully community-minded. –  Mike Williamson Dec 6 '12 at 1:02
@Mike The comment is directed at this answer. Which proposes some elaborate algo that is very off topic here. –  David Heffernan Dec 6 '12 at 7:25
@David: Ah, gotcha, my bad. Regardless, while the citations might be a bit much, I still like Morten's algo. It is succinct, which is hard to learn at first, but a great skill to develop. He also returns the evaluation instead of a separate T/F statement, also great to get the head around. And he hints that a "trial division" is not really that efficient. –  Mike Williamson Dec 13 '12 at 17:52
show 1 more comment

Your function actually returns whether your number is odd.

Indeed, what you're doing is you're checking whether 2 divides your number, and return immediately. You never check for the other numbers.

What you need to do is take this return true out of the if's else clause and the for loop back into the main function body.

On a sidenote, If you're looking for the primes lower than a given number, you could store the primes you found in memory and then only try dividing you new number by those primes ! (because if d is composite and divides q, then p exists such that p is prime and p divides q).

share|improve this answer
add comment

The problem is that you put return False in the else clause rather than at the end of the function. So your function will return right after the first divisor is checked, rather than going on to check other divisors.

Here is a simple primality test similar to yours:

def is_prime(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return n > 1
share|improve this answer
(I didn't downvote, but...) Computing the square root once is bound to be cheaper than squaring n times. Also, while loops aren't very Pythonic; use range(). –  Marcelo Cantos Nov 5 '11 at 9:50
I agree range is more pythonic, but OTOH integer multiplication is cheap, and the sqrt approach requires rounding up, which seems inelegant to me. –  Daniel Nov 5 '11 at 9:57
The next integer above the square root doesn't divide n. It is therefore safe to round down, which is as simple as casting to int. Besides, I'll favour O(sqrt(N)) over O(N) any day of the week, elegance be damned (within reason, of course). –  Marcelo Cantos Nov 5 '11 at 10:01
You're right, a cast to int works fine. But this code is also O(sqrt(n)), and probably at least as fast since it doesn't have the overhead of list lookups (for python 2) or iterators (for 3). –  Daniel Nov 5 '11 at 10:06
Duuuhh. My brain's half-on, half-off tonight. –  Marcelo Cantos Nov 5 '11 at 10:19
add comment

Your Answer


