A prime number must satisfy three conditions:

- it must be a natural number (so numbers like 1.2, -7, or √3 are out of the question);
- it must be greater than 1;
- it must not be the product of any two other numbers.

So essentially, a prime number is any natural number starting from 2 that isn’t divisible with any numbers other than 1 or itself. For instance:

- 5 is a prime number, it can only be written as a product of 1 x 5;
- 6 is not a prime number, it can be written as 2×3.

A number that is not *prime* is called *composite*. All natural numbers are either *primes* or *composites*.

Contents

### Understanding the basics of prime numbers

All natural numbers are either primes or composites — but what does that really mean? Well, it basically means that if we take any natural number, it can be either written as a product of two other numbers, or it’s a prime. There’s no middle way. If we look at the image above, 12 is written as 4 x 3. It can also be written as 6 x 2, but it doesn’t matter.

Whether there’s one way to write a number as a product or a million ways to write it as a product, it’s still a composite number, and therefore not prime.

Every prime number can only be written as ‘1’ times itself. Every composite number can be written as a product of prime numbers (something called prime factorization).

### Checking if a number is a prime

The rough way to search for prime numbers is to take any number and try and see if any numbers divide it evenly. In other words, if it has any divisors other than 1 and itself, it’s not prime.

But we can get a bit more clever about our search for prime numbers.

We can weed out half of them right from the start. How? By using the number ‘2’. Every number is either odd or even, by definition. Even numbers are divisible by 2, which means they can be written as 2 times *something* — and are therefore composite, not prime. The number ‘2’ is the only even prime number.

With the odd numbers, we can use a similar approach, but using other numbers instead of ‘2’. For instance, ‘3’ is a prime number, so it can be used to weed out other numbers that aren’t prime. This is actually a very old algorithm used to discover prime numbers: you start from 2, and then every prime number you encounter, you use it to weed out its multiples. You don’t need to use ‘4’ since it is an even number, and we already know that other than ‘2’, no prime number is even. So we can just move on to 5, 7, and move on. This is called a ‘sieve’, and commonly, the ‘sieve of Eratosthenes’, since the ancient Greek mathematician Eratosthenes first described it. You can see a visual representation of how it works in the image below:

You can get a bit more clever with your prime-finding sieves too. For instance, let’s say you want to check if the number 100 is prime (spoiler alert, it’s not). You don’t need to check every number from 2 to 100, you can stop with your checks at 50, which is the half of 100. Why? Look at it this way:

- every number can be written as: number (n) = ‘half’ x 2. Every number is twice its half. If you reach a number beyond ‘half’ of n’s value, you’d need to multiply it by something smaller — but there’s nothing smaller than 2. So you don’t need to look further than the half of the number.

We can get even smarter than this: you don’t even need to check until half of the number, you only need to check to its square root (√n).

Looking for prime number is a common exercise not just in mathematics, but also in programming, where the goal is learning how to devise and optimize an algorithm.

A list of prime numbers up to one thousand:

2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | |

29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 |

71 | 73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 |

113 | 127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 |

173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 |

229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |

281 | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 |

349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 |

409 | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 |

463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 |

541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 |

601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 |

659 | 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 |

733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 |

809 | 811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 |

863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 |

941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |

### Some properties of prime numbers

Prime numbers may seem like just a new quirk, but mathematicians have been fascinated with them for millennia (as we’ll see in a bit). They have several properties that make them special — here are just a few of them.

**There are infinite prime numbers**

The sequence of prime numbers never ends. It can get harder and harder to find prime numbers, but there will always be an even larger one. This was first proven by the Ancient Greek mathematician Euclid. The longest prime number we know of is 22 million digits long.

**There is no efficient formula for calculating prime numbers**

Mathematicians have devised several ways of encoding or looking for prime numbers, but none of them are very efficient. This is one of the things that makes prime numbers so attracticve. We don’t know when and how prime numbers occur, we can just calculate them.

**1 is not technically a prime number**

This sometimes starts weird debates and is not truly consequential, but 1 is not typically considered a prime number. There’s no strict reason for that, however. Ancient Greeks (and Arabic mathematicians as well) did not consider 1 to be a number in the sense that all other numbers are — it was more a unit for numbers than a number itself. In the 18th and 19th centuries, some mathematicians considered it prime, while others did not. Nowadays, we don’t really consider it a prime, if only for the fact that we would have to rewrite the definition of prime numbers in a way that’s more awkward.

**Numbers can be prime among themselves (but not technically primes)**

Two numbers that don’t have any common divisors are considered to be ‘coprime’ — and this doesn’t really mean that they are really primes (though they can be). For instance, the numbers 25 and 4 are coprimes, because 25=5×5, while 4=2×2, and they have common divisors.

### History of prime numbers

You may think that prime numbers are a modern quirk that mathematicians came up with, but they’ve actually fascinated people for centuries — nay, millennia. An Egyptian papyrus dating from 3,550 years ago references prime numbers, and Euclid’s landmark *Elements *work demonstrates that there are infinitely many prime numbers. Several well-known Greek mathematicians dealt with prime numbers, including Eratosthenes, whose sieve we’ve just looked at.

Coincidentally or not, the period in which people didn’t seem really interested in prime numbers is a period we now call the Dark Ages. Some Islamic mathematicians looked at prime numbers, which Fibonacci brought to Europe, translating and analyzing the work. After that, most brilliant mathematicians looked at prime numbers: Pierre de Fermat stated (but did not prove) Fermat’s little theorem, which was later proved by Leibniz and Euler.

Many mathematicians have also tried to find ways to predict the emergence of prime numbers, but this has proven a hidden Graal. Since 1951, all the largest known prime numbers have been discovered using computers.

### Why prime numbers matter so much

For a very long time, prime numbers were canonical and pure — a quirk of mathematics, but with little significance outside of mathematics. Now, we know this to be untrue and prime numbers have important applications in several fields.

For instance, the number of cogs on two gears is often chosen to prime among themselves, to create an even contact between every cog of both wheels and avoid unnecessary wear and damage — but this is not technically an application of prime numbers.

The moment when primes became really important was in the 1970s when it was first announced that prime numbers could serve as the basis of public-key cryptography algorithms. In other words, every time you use the internet to send an encrypted message (like you probably do daily), it uses an algorithm based on prime numbers, specifically because they’re so mysterious and hard to assess.

Prime numbers also play a part in fields such as quantum mechanics and abstract algebra. Perhaps even more intriguing, prime numbers have been shown to also play a role for some biological species. The cicadas of the genus Magicicada, for instance, spend most of their time as grubs beneath the ground. They emerge after 7, 13, or 17 years — all prime numbers. This is not a coincidence, biologists believe: cicadas emerge in this fashion to prevent predators from synchronizing with their lifecycle. In addition to the many applications of prime numbers in mathematics, modern research seems to indicate that at least in some cases, prime numbers also play a role in other fields.

Prime number research is far from over. Undoubtedly, there are many more prime mysteries waiting to be uncovered — this is only scratching the surface.