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
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.
time complexity is O(sqrt(N))
space complexity is O(1)
The point of this question is to make sure that you only iterate up to (including) sqrt(N).
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.