HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonModerate

Prime number checker in Python 3 - follow-up

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewprimesstackoverflowperformancepythonpython-3.x
numberfollowpythonprimechecker

Problem

I have updated my code from the last time it got reviewed. If anyone has some more suggestions on how I can improve this and/or make it faster it would be appreciated!

def is_prime(num):
    '''Calculates whether num is a prime number,
    if it is return True otherwise return False'''

    # SPECIALCASE: These are special cases that are not primes
    if num % 2 == 0 and num != 2 or num <= 1:
        return False

    # Look for a factor
    for i in range(3, int(num ** (0.5)) + 1, 2):
        # If there is a factor
        if num % i == 0:
            # Its not a prime number
            return False

    # If there is no factors and its not a special case
    return True

Solution


  1. Overview



Your code is well written and what it does is clear. However I will argue that if you want a drastic increase in performance, you need to switch your algorithm. Testing primality can be done in polynomial time, but is generally a problem which requires sophisticated math. The problem can be solved in polynomal time as shown by the AKS_primality_test. However there are far faster algorithms than this one. As you can see, it is not the easiest thing to understand without a background in higher mathematics.

  • A review of your algorithm



  • Show a probabilistic approach



  • Compare your algorithm, the probabilistic, and the isprime function from the primefac package.



  1. Review



As your code is fairly short, there is not much to comment on. I really like that you use a docstring in the beginning of your code to document it. The code looks good.

  • Use the if __name__ == "__main__": module. It makes it easier to test and easier to import.



  • Some of the comments are unnecessary and there is too much space in the last return.



  • The num



One way to handle this could be 

try:
    int(num)
except ValueError:
    raise ValueError("Ops. Input must be a positive integer")
if int(num) != num or num < 0:
    raise ValueError("Ops. Input must be a positive integer")

if num in [0, 1]: return False


The last line could also have been written as

if num <= 1: return False


Since we have already tested that num => 0. However I prefer the first version as it is much clearer what it actually checks. You should always try to make it as clear as possible what you want to catch.

1.1 Some improvements on the algorithm

Say you check some number with your algorithm. If the number is not divisible by \$3\$ you do not need to ever check any multiples of \$3\$ again. Yet your code checks \$6\$, \$9\$ and so forth. A better approach would be to iterate over the numbers not divisible by \$2\$ or \$3\$. This removes the checking of \$2/3\$ of all numbers in comparison to only removing \$1/2\$. So, what numbers are not divisible by \$3\$ or \$2\$? Well all numbers are on the form \$6k+1\$, \$6k+2\$, \$6k+3\$, \$6k+4\$ or \$6k+5\$. Since they are either \$0\$, \$1\$, \$2\$, \$3\$, \$4\$ or \$5\$ numbers away from being a multiple of \$6\$. This means that only numbers on the form \$6k+1\$ or \$6k+5\$ are not divisible by \$2\$ or \$3\$.

Implementation is simple increase counter by \$6\$, test \$+1\$ and \$+5\$.

primes_to_remove = [2, 3, 5]
for prime in primes_to_remove:
    if num == prime: return True
    elif num % prime == 0: return False

# Look for a factor
limit = int(num**(0.5))+1
for multiple in range(6, int(num**(0.5))+1, 6):
    for k in [1, 5]:
        # If there is a factor
        if num % (multiple+k) == 0:
            # Its not a prime number
            return False


This can further be generalized by removing [2, 3, 5] as shown below

primes_to_remove = [2, 3, 5, 7, 11, 13, 19, 23, 29]
for prime in primes_to_remove:
    if num == prime: return True
    elif num % prime == 0: return False

# Look for a factor
limit = int(num**(0.5))+1
for multiple in range(30, int(num**(0.5))+1, 30):
    for k in [1, 7, 11, 13, 19, 23, 29]:
        # If there is a factor
        if num % (multiple+k) == 0:
            # Its not a prime number
            return False
return True


This idea of removing the first primes can again be modified into removing [2,3,5,7] and then check the remaining numbers. However the advantages of this method quickly diminish for larger primes as we are removing fewer and fewer numbers. As a last example, it is possible to only iterate over the primes. From the primesieve library we can import a prime generator.

from primesieve import Iterator

def is_prime_primegenerator(num):
    it = Iterator()
    prime = it.next_prime()

    # Iterate over the primes below sqrt(n)
    limit = int(num**(0.5))+1
    while prime < limit:
        prime = it.next_prime()
        if num % prime == 0:
            print num, prime
            return False
    return True


This is the best we can do following down your path of checking primes from the smallest to the largest. It assumes however that the next_prime() is extremely fast. Which it luckily is.

Using the 235 version of the sieve above, it gave me a \$2.5\$ times speed increase of your code. Putting it all together gives

``
def is_prime(num):
'''Calculates whether num is a prime number,
if it is return True otherwise return Flase'''

try:
int(num)
except ValueError:
raise ValueError("Ops. Input must be a positive integer")
if int(num) != num or num < 0:
raise ValueError("Ops. Input must be a positive integer")

# SPECIALCASE: These are special cases that are not primes
if num in [0, 1]: return False

primes_to_remove = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
for prime in primes_to_remove:
if num == prime: return True

Code Snippets

try:
    int(num)
except ValueError:
    raise ValueError("Ops. Input must be a positive integer")
if int(num) != num or num < 0:
    raise ValueError("Ops. Input must be a positive integer")

if num in [0, 1]: return False
if num <= 1: return False
primes_to_remove = [2, 3, 5]
for prime in primes_to_remove:
    if num == prime: return True
    elif num % prime == 0: return False

# Look for a factor
limit = int(num**(0.5))+1
for multiple in range(6, int(num**(0.5))+1, 6):
    for k in [1, 5]:
        # If there is a factor
        if num % (multiple+k) == 0:
            # Its not a prime number
            return False
primes_to_remove = [2, 3, 5, 7, 11, 13, 19, 23, 29]
for prime in primes_to_remove:
    if num == prime: return True
    elif num % prime == 0: return False

# Look for a factor
limit = int(num**(0.5))+1
for multiple in range(30, int(num**(0.5))+1, 30):
    for k in [1, 7, 11, 13, 19, 23, 29]:
        # If there is a factor
        if num % (multiple+k) == 0:
            # Its not a prime number
            return False
return True
from primesieve import Iterator

def is_prime_primegenerator(num):
    it = Iterator()
    prime = it.next_prime()

    # Iterate over the primes below sqrt(n)
    limit = int(num**(0.5))+1
    while prime < limit:
        prime = it.next_prime()
        if num % prime == 0:
            print num, prime
            return False
    return True

Context

StackExchange Code Review Q#133280, answer score: 12

Revisions (0)

No revisions yet.