Ad
McCodevs.McCode

Fast Primality Test in Python

We can turn this into a one-liner (minus the import)

Code
Diff
  • from math import sqrt

is_prime = lambda n: n == 2 or (n > 2 and n % 2 != 0 and all(n % x != 0 for x in range(3, int(sqrt(n)) + 1, 2)))
    • from math import sqrt
    • is_prime = lambda n: n == 2 or (n > 2 and n % 2 != 0 and all(n % x != 0 for x in range(3, int(sqrt(n)) + 1, 2)))
    • def is_prime(n):
    • if n < 2:
    • return False
    • elif n == 2:
    • return True
    • elif n % 2 == 0:
    • return False
    • for x in range(3, int(sqrt(n)) + 1, 2):
    • if n % x == 0:
    • return False
    • return True
McCodevs.raulbc777

Fast Primality Test in Python

You can cut the time it takes to test large(-ish) numbers roughly in half by not testing for divisibility by even numbers other than 2. We don't need to test for divisibility by the other even numbers because if a number were divisible by an even number greater than 2, it would have already been divisible by 2.
We can accomplish this by making divisibility by 2 a special case and instead starting the loop at 3 with a step size of 2.

Code
Diff
  • from math import sqrt


def is_prime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for x in range(3, int(sqrt(n)) + 1, 2):
        if n % x == 0:
            return False
    
    return True
    • from math import sqrt
    • def is_prime(n):
    • if n < 2: return False
    • for x in range(2, int(sqrt(n)) + 1):
    • if n % x == 0: return False
    • if n < 2:
    • return False
    • elif n == 2:
    • return True
    • elif n % 2 == 0:
    • return False
    • for x in range(3, int(sqrt(n)) + 1, 2):
    • if n % x == 0:
    • return False
    • return True