A prime number is a natural number greater than $1$ which has no positive divisors other than $1$ and itself. This article covers different algorithms for checking if a number is prime or not, including a naive test, the Eratosthenes Sieve, the Euler Primality Test, and the Miller-Rabin Primality Test.

The Eratosthenes Sieve is an algorithm to find prime numbers up to a positive number $n$ using $O(n)$ space.