How Do You Find Prime Numbers?

To find prime numbers, test whether a number has any divisors other than 1 and itself. The Sieve of Eratosthenes finds every prime up to a chosen limit by crossing out multiples, while trial division checks a single number for factors up to its square root. There is no simple formula that produces all primes.

Beautiful anomalies occur in every subject, but if there is one area of beauty that most mathematicians would agree upon, it is the prime number.

To ordinary folk, these might look like a random set of numbers in the vast array of numbers that we can comprehend. However, these numbers hold a unique pedestal in mathematics, especially in the field of number theory. Great minds have poured countless investigative hours into this issue, including great minds like Paul Erdős, G.H. Hardy and Srinivasa Ramanujan, to name but a few. Now, before we dive into the different algorithms to find prime numbers, let’s first establish a preliminary understanding of prime numbers.

What Are Prime Numbers?

The most technical definition of a prime number is that it is a natural number greater than 1 and can only be obtained by multiplying 1 and itself. If natural numbers were to be understood more intuitively, we could state that these are numbers we use to count.

To understand this more precisely, let’s pick two numbers, 5 and 6. Now, 5 is a number that can only be obtained by the multiplication of 1 and 5 (the number itself). However, when we take the number 6, we notice that it can be obtained in another way, apart from multiplying 1 and 6 (the number itself). It can also be obtained by multiplying the numbers 2 and 3, which means it is not a prime number. A number that isn’t a prime number is known as a composite number. By convention, 2 is the smallest prime and the only even prime, since every other even number is divisible by 2.

The Sieve Of Eratosthenes And Trial Division

Before we get to the exotic, record-breaking primes, let’s answer the question most people are actually asking: how do you find prime numbers in the first place? The honest answer is that there is no neat formula you can feed a counter into and have it spit out the next prime. Mathematicians have hunted for one for centuries, and every tidy candidate eventually breaks. Instead, we test numbers for divisibility, and two classic methods do most of the heavy lifting.

If you want all the primes up to some limit, the oldest and simplest tool is the Sieve of Eratosthenes, named after the Greek mathematician Eratosthenes of Cyrene, who also famously estimated the circumference of the Earth. Write out every number from 2 up to your limit. Circle 2 (it’s prime), then cross out every multiple of 2. Move to the next number still standing, which is 3, circle it, and cross out every multiple of 3. Repeat with 5, then 7, and so on. Whatever survives the crossing-out is prime. Say you stop at 30: after sieving, the numbers left standing are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. A handy shortcut is that you only need to sieve using primes up to the square root of your limit (here, up to about 5.5, so just 2, 3 and 5), because any composite number below the limit must already have a smaller factor that has done the crossing out for you.

If you only want to check a single number, you use trial division. To test whether a number n is prime, try dividing it by each prime starting from 2. If none of them divides evenly, n is prime. The same square-root trick keeps the work manageable: you never have to test divisors larger than √n. Take 97, for example. Its square root is just under 9.85, so you only need to try 2, 3, 5 and 7. None of them divides 97 cleanly, so 97 is prime. That’s a far cry from blindly checking all 96 numbers beneath it. These two methods are the workhorses for everyday prime finding; the Mersenne and Fermat approaches that follow are really about chasing a few very special, very large primes.

Mersenne Prime Method

The Mersenne Prime Method is a special method of finding a particular kind of prime, known as the Mersenne Primes. The name for this method is derived from the French monk, Marin Mersenne, who studied them in the early 17th century. A Mersenne prime is a prime that can be written in the form 2ⁿ-1, where the exponent n must itself be a prime number. Be careful not to confuse the two: the exponents that produce the first Mersenne primes are 2, 3, 5, 7, 13, 17, 19, 31, 61 and 89, but the Mersenne primes themselves are 3, 7, 31, 127, 8191, and so on (for example, 2⁵-1 = 31). A prime exponent doesn’t guarantee a Mersenne prime either: 2¹¹-1 = 2047 = 23 × 89, which is composite. For a long time, hunting for Mersenne primes was a drudgery, as it grows highly computation-intensive once you move on to higher exponents.

However, with the advent of computers, they could now perform these number-crunching calculations, which had formerly been done by humans in the most painstaking and time-consuming fashion. We’ve definitely reached higher Mersenne Primes and primes on an overall level. The search for primes is just as fervent as other numerical searches done by computers. Another numerical search, similar to the drive for primes, lies in furthering the decimal places in certain irrational numbers, such as pi (the ratio of the circumference to the diameter). However, the continual search for the next largest prime is substantially more difficult than the search for the next digit of pi.

Even the largest computers (supercomputers) take a substantial amount of time to verify if a new number (which is usually mind-bogglingly huge) is a prime in itself, and it takes even more time to check if the number is a Mersenne Prime. For this reason, Mersenne numbers have been of great interest in the field of Cybersecurity and Cryptography, especially pertaining to encryption.

In August 2008, Edson Smith, a system administrator at UCLA, found the largest prime number known to that point. Smith had installed software for the Great Internet Mersenne Prime Search (GIMPS), a volunteer-based distributed computing project. The number was a Mersenne Prime, 2^43,112,609-1, that is 12,978,189 digits long. To give some perspective as to how large that is, it would take nearly two-and-a-half months to write it out and, if printed, would stretch for roughly 48 km (30 miles).

That record has since been shattered several times over. As of 2024, the largest known prime is 2^136,279,841-1, a Mersenne prime with a staggering 41,024,320 digits. It was discovered on October 12, 2024 by Luke Durant, a former Nvidia engineer who ran GIMPS software across thousands of cloud GPUs, and it became only the 52nd Mersenne prime ever found. Reading the whole thing aloud would take you the better part of a year.

Fermat’s Prime Number Method

A Fermat number is related to, but distinct from, a Mersenne number. The name stems from the 17th century mathematician and lawyer, Pierre de Fermat. A Fermat number looks similar to a Mersenne number, with one little tweak: instead of subtracting 1 from a power of 2, you add it. A Fermat number F_n is defined as 2 raised to the power 2ⁿ, plus 1. In other words, F_n = 2⁽²ⁿ⁾ + 1. The exponent is itself a power of 2, which is why these numbers balloon so quickly.

Fermat was of the firm belief that every number of this form was prime, and he conjectured that the formula would produce a prime for every value of n. As it turns out, he was wrong, but it took the genius of Leonhard Euler to prove it. What makes these numbers beautiful, yet tricky, is that they grow extremely large very fast, even within the first few iterations. To see this, let’s take n as the values n = 0, 1, 2, 3 and 4.

When n = 0, the exponent 2⁰ = 1, so F₀ = 2¹ + 1 = 2 + 1 = 3, which is prime. When n = 1, the exponent 2¹ = 2, so F₁ = 2² + 1 = 4 + 1 = 5, which is prime. When n = 2, the exponent 2² = 4, so F₂ = 2⁴ + 1 = 16 + 1 = 17, which is prime. When n = 3, the exponent 2³ = 8, so F₃ = 2⁸ + 1 = 256 + 1 = 257, which is prime. When n = 4, the exponent 2⁴ = 16, so F₄ = 2¹⁶ + 1 = 65,536 + 1 = 65,537, which is prime. Now, as you can observe, by the time we reach F₅ the value has already jumped to 2³² + 1 = 4,294,967,297.

And here is where Fermat’s conjecture falls apart. In 1732, Euler showed that this very number is not prime: 4,294,967,297 = 641 × 6,700,417. F₅ is composite, and so is every Fermat number that has been fully tested since. In fact, F₀ through F₄ remain the only Fermat primes anyone has ever found, and no one knows whether there are any others. It is a humbling reminder that even a brilliant pattern can mislead you, and that the search for prime numbers will always go to infinity, and beyond!