efficient ways to check prime number in Python

Question

Here is my code, and pretty brute force. Seeking smarter solutions. I remember there are some theory in Number Theory to check whether a number is a prime number with high efficiency, but cannot find it out. Anyone have smarter ideas are appreciated.

def isPrimeNumber(self, num):
    i = 2
    while (i <= num / 2):
        if num % i == 0:
            return False
        i = i + 1

    return True

thanks in advance, Lin

Where have you searched? Obvious optimizations are using the square root of `num` as a limit (inclusive), and skipping even numbers that are not 2. — Reut Sharabani, Sep 12 '15 at 23:07
@ReutSharabani, not sure if AKS algorithm is better efficiency? https://en.wikipedia.org/wiki/AKS_primality_test, I cannot find a Python implementation, let me know if you have one. :) — Lin Ma, Sep 13 '15 at 00:33

score 1 · Answer 1 · answered Sep 12 '15 at 23:07

1

One huge and simple optimization you can do to your code is to stop looking for divisors when you reach the square root of your num.

answered Sep 12 '15 at 23:07

Ronald Kaiser

61
7

thanks, not sure if AKS algorithm is better efficiency? https://en.wikipedia.org/wiki/AKS_primality_test, I cannot find a Python implementation, let me know if you have one. :) – Lin Ma Sep 13 '15 at 00:33

score 1 · Accepted Answer · answered Sep 12 '15 at 23:20

1

It's Improve performance. And loop occur till square root of this number
You can try this:

import math
def isPrimeNumber(self, num):
    for i in range(2, sqrt(num)):
        if num % i == 0:
            return False

    return True

answered Sep 12 '15 at 23:20

Sakib Ahammed

2,452
2
25
29

not sure if AKS algorithm is better efficiency? https://en.wikipedia.org/wiki/AKS_primality_test, I cannot find a Python implementation, let me know if you have one. :) – Lin Ma Sep 13 '15 at 00:32

efficient ways to check prime number in Python

2 Answers2