Write an algorithm for testing primality, i.e. given n, the algorithm must decide if n is a prime.
What is the running time of your algorithm in terms of n? Use big-Oh notation. Note that the input size is the size of the decimal representation of n.