# Primality Test

A **prime number** (or a **prime**) is a natural number greater than `1` that 
cannot be formed by multiplying two smaller natural numbers. A natural number 
greater than `1` that is not prime is called a composite number. For 
example, `5` is prime because the only ways of writing it as a 
product, `1 × 5` or `5 × 1`, involve `5` itself. However, `6` is 
composite because it is the product of two numbers `(2 × 3)` that are 
both smaller than `6`. 

![Prime Numbers](https://upload.wikimedia.org/wikipedia/commons/f/f0/Primes-vs-composites.svg)

A **primality test** is an algorithm for determining whether an input 
number is prime. Among other fields of mathematics, it is used 
for cryptography. Unlike integer factorization, primality tests 
do not generally give prime factors, only stating whether the 
input number is prime or not. Factorization is thought to be 
a computationally difficult problem, whereas primality testing 
is comparatively easy (its running time is polynomial in the 
size of the input). 

## References

- [Prime Numbers on Wikipedia](https://en.wikipedia.org/wiki/Prime_number)
- [Primality Test on Wikipedia](https://en.wikipedia.org/wiki/Primality_test)