What are prime numbers and why they matter — yes, even in your day to day life

Prime numbers are one of the most fascinating mysteries of mathematics, and the more we look at them, the weirder they get.

 by Mihai Andrei

 

 January 21, 2021

 

in Feature Post, Mathematics

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.

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: