---
title: Prime Numbers
---
## Prime Numbers

A [natural number](https://en.wikipedia.org/wiki/Natural_number) greater than 1 is called a *prime number* if it cannot be written as a product of two smaller natural numbers. A natural number that is not a prime number is called a composite number.

For example, 5 is a prime number because the only way to write it as a product of natural numbers is 5\*1 or 1\*5. On the other hand, 6 is  not a prime number because 6 = 2\*3. No even number greater than 2 is prime, but there are [infinitely many](https://en.wikipedia.org/wiki/Euclid%27s_theorem) prime numbers, the first ten of which are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. The largest known prime number ([as of October 2018](https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search)) is 2^77232917 - 1.

Despite seeming simple, prime numbers are incredibly important in [cryptography](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) used by [banks](https://crypto.stackexchange.com/questions/13235/how-do-institutions-like-banks-do-rsa-with-big-primes) and [secure shell protocols](https://www.ssh.com/ssh/host-key) because of how difficult they are to find and work with.

For example, there are no '[fast](https://en.wikipedia.org/wiki/General_number_field_sieve)' ways to find prime factors, so while finding the prime factors of 6 above is easy, it is only easy because 6 is small. Finding the prime factors of a number with hundreds or thousands of digits, however, is exceptionally time consuming when there are no [polynomial time](https://en.wikipedia.org/wiki/Time_complexity#Superpolynomial_time) algorithms.

12 is a not a prime number as it can be divided evenly by 1, 2, 3, 4, 6, and 12.

The first ten prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

![alt text](https://cdn.britannica.com/04/183104-004-DC24F17A.jpg)

**This is a chart with the first 100 natural numbers, indicating which are prime and which are composite.**

<!-- The article goes here, in GitHub-flavored Markdown. Feel free to add YouTube videos, images, and CodePen/JSBin embeds  -->

<!-- Please add any articles you think might be helpful to read before writing the article -->

There is no formula for primes, i.e., there is no formula that you can plug any natural number `n` in and get the `n-th` prime from it. The distribution of primes is unknown, i.e., after the `n-th` prime there is no formula for how much larger the `(n+1)-th` prime is. However, it is known that there are [arbitrarily large](https://math.stackexchange.com/a/1675495/12133) gaps between consecutive primes. It is also known that there are infinitely many pairs of consecutive primes that differ by [at most 246](https://en.wikipedia.org/wiki/Twin_prime#History).