welcome to
evildojo


HackerRank

Cracking the Coding Interview

Time Complexity: Primality

Located here: https://www.hackerrank.com/challenges/ctci-big-o

Notes:

This example is done in Python.


Not formatting the problem text. Read the link. I am too lazy.


My final solution:

from math import sqrt

input_array = []
p = int(raw_input().strip())
for _ in xrange(p):
    n = int(raw_input().strip())
    input_array.append(n)

def isPrime(n):
    if n == 2 or n == 3: 
        return True
    if n < 2 or n%2 == 0:
        return False
    if n < 9:
        return True
    if n % 3 == 0:
        return False
    r = int(n ** 0.5)
    f = 5
    while f <= r:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f = f + 6
    return True

for i in input_array:
    if isPrime(i):
        print("Prime")
    else:
        print("Not prime")

I can walk you through how I arrived here over the course of a couple days.

Naive (and wrong):

def is_prime(num):
     if num <= 2:
        return False
     if num % 2 == 0 and num > 2:
         return False
     i = 3
     while i < num / 2:
        if num % i == 0:
            return False
        i = i + 2
     return True

This was copy/pasted, not realizing / forgetting that the check was against sqrt(num), not num/2.

The essential gist of a primality test is to check that the only thing that can divide a number is 1 and itself.

Due to computation-time there are speed-ups we can perform on our algorithms.

The solution I used was pulled from stackoverflow, but originally I thought I would need a sieve.

Using a sieve produced runtime errors on Hackerrank, so I removed it and the solution worked.