Determining Prime is too slow

Question

So I solved a problem on code wars but it's just too slow and inefficient. Here's the code I wrote:

def is_prime(number):
if number > 1:
    for i in range(2, number):
        if number % i == 0:
            return False
            break
    else:
        return True
else:
    return False

Is there any way to make it fast?

post the question in [Code Review](https://codereview.stackexchange.com/) — deadshot, Sep 05 '20 at 09:49
Why not browse through the thousands of other questions on here about detecting prime numbers? — khelwood, Sep 05 '20 at 09:50
Hint: you are looping up to the number when you only need to loop up to the square root. Another comment: your `break` statement cannot be reached. — alani, Sep 05 '20 at 09:52

Christian Sloper · Accepted Answer · 2020-09-05T10:02:04.340

2

There are several easy speedups to this:

a) with the exception of 2, all primes are odd, so you can iterate in steps of 2.
b) all non-primes must have at least one factor smaller than or equal to the square root of n, so you only need to check numbers up to square root of n.

Add those, if that isn't fast enough there are many other speedups to check out. Also check out probabalistic primality tests like Miller-Rabin.

Comments to this post include:

All primes > 3 are congruent to 1 or 5 (mod 6), so you can iterate in steps of 6 and check two numbers at a time.

edited Sep 05 '20 at 10:02

answered Sep 05 '20 at 09:53

Christian Sloper

7,440
3
15
28

"up to n" looks like a typo (especially in view of what you just said about square root) – alani Sep 05 '20 at 09:54
you are completely right of course. i have edited. – Christian Sloper Sep 05 '20 at 09:55
"smaller then the square root" —> "smaller than or equal to the square root" – khelwood Sep 05 '20 at 09:55
1

With the exception of 2 and 3, no primes are not of the form `6n+/-1`, so you can start at 5 and alternately add 2 and 4: 5, 7, 11, 13, 17, 21, 23, etc. You still have to check primality but the sample space is smaller than just `2n+3` - you'll end up checking 1/3 less candidates – paxdiablo Sep 05 '20 at 09:55
@paxdiablo True, or if easier, iterate in steps of 6 and check two factors per iteration. – alani Sep 05 '20 at 09:58

score 1 · Answer 2 · edited Sep 05 '20 at 10:03

1

Most modern computers use have more then one core, so if you make it run in parallel utilizing all cores it should go faster.

You can just divide the ranges between cores, say if you have 10 core, then each core can check the modules of the core number number.

Also another easy way to doubble the speed is to ignore even numbers.

edited Sep 05 '20 at 10:03

olle.holm

233
1
4
11

answered Sep 05 '20 at 09:59

banankontakt

198
9

score 0 · Answer 3 · answered Sep 05 '20 at 10:02

Also you would only have to check in range of half the number because dividing through half the number would result in 2 and dividing through 1 result in the number itself so everything between must be a number between 1 and 2, you don’t need to check that for a prime number

Determining Prime is too slow

3 Answers3