10

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)
    odd.remove(1)
    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
            else:
                    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.

Improve this question
10
  • 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, ...). Commented Nov 5, 2011 at 9:44
  • 2
    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. Commented Nov 5, 2011 at 9:45
  • 1
    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. Commented Nov 5, 2011 at 9:48
  • 1
    @PaulManta range doesn't accept float, which sqrt(n) returns, and casting to int messes up the result due to rounding error. Commented Nov 5, 2011 at 9:53
  • 1
    Related: Does a library for prime-related functions exist for Python? Commented Sep 15, 2018 at 13:16

4 Answers 4

Reset to default
15

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)))

Edit: Here's a more educational version because the first solution is very condensed and perhaps harder to read:

from math import sqrt
def prime(a):
    if a < 2: return False
    for x in range(2, int(sqrt(a)) + 1):
        if a % x == 0:
            return False
    return True

I've substituted in sqrt(a) in place of a ** 0.5 to make things more clear. The square root is used to not look at more factors than we have to.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

The problem says I have to use trial division.
This is homework. The exercise is a means to teach programming!
@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.
@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.
@MikeWilliamson The succinctness here is very bad. Much better is to use a few more lines and add some explanatory variables. Excessive succinctness is a terrible failing of many programmers. If this was spread out properly on 4 or 5 lines it would be much quicker to read. Much easier to read. Much easier to check. For a beginner, like the person asking the question, the code in this answer is black magic.
|
12

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
    else:
        return True

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

Improve this answer

5 Comments

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.
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.
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).
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.
That's 2 years ago. I guess the reason was to keep the change to the minimum.
2

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).

Improve this answer

Comments

2

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
Improve this answer

5 Comments

(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().
I agree range is more pythonic, but OTOH integer multiplication is cheap, and the sqrt approach requires rounding up, which seems inelegant to me.
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).
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).
Duuuhh. My brain's half-on, half-off tonight.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.