##### 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.

##### Link

##### Complexity:

time complexity is O(sqrt(N))

space complexity is O(1)

##### Execution:

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

##### Solution:

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

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.