evildojo

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.