We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Time Complexity: Primality
  2. Discussions

Time Complexity: Primality

  • carsonlmh
     + 10 comments

    Basic Python 3 solution:

    from math import sqrt 

def isPrime(p):
    if p < 2:
        return False
    elif p <= 3:
        return True
    elif p % 2 == 0 or p % 3 == 0:
        return False
    else:
        for i in range(3, int(sqrt(p)+1), 2):
            if p % i == 0:
                return False
    return True
    • We only need to check up to square root of p.
    • We iterate over the range in increments of 2 for odd numbers only because even numbers are not prime except for 2.