Primes are of great theoretical and practical value in cryptography. A
primality test is an algorithm for determining whether an input number is
prime or not.
Naive but deterministic
The simplest primality test is trial division: given an input number,
$n$, check whether it is divisible by any prime number between 2 and $\sqrt{n}$. If
so, then $n$ is composite. Otherwise, it is prime.
The prime number theorem: the distribution of primes is $Ï€(n) \sim n/\log(n)$
where $Ï€(n)$ is the prime-counting function (the number of primes less than or
equal to $n$) and $\log(n)$ is the natural logarithm of $n$.