HackerRank 'Time Complexity: Primality' Solution

Martin Kysel · July 26, 2020

Short Problem Definition:

A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given n integers, determine the primality of each integer and print whether it is Prime or Not prime on a new line.

Note: If possible, try to come up with an O(sqrt(N)) primality algorithm, or see what sort of optimizations you can come up with for an O(N) algorithm.

Time Complexity: Primality


time complexity is O(sqrt(N))

space complexity is O(1)


The point of this question is to make sure that you only iterate up to (including) sqrt(N).

def primality(n):
    if n == 1:
        return False

    for i in xrange(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

Twitter, Facebook