Testing for prime numbers has long been an interesting mathematical challenge. Due to the popular use of cryptography, there exists important applications for finding large primes. We present a survey of primality testing algorithms ending with an algorithm originally proposed by Agrawal, Kayal, and Saxena (AKS) in their paper, ''PRIMES is in P''. The AKS algorithm is the first deterministic polynomial-time primality-proving algorithm. We then do an analysis on the runtime of this algorithm and present observations as well as suggestions for improvements to the algorithm.