Located here: https://www.hackerrank.com/challenges/ctci-big-o
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.