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