Prime Number Calculator

Prime Numbers

This calculator checks if some number is prime or not.

The definition of a prime number is any natural number greater than 1 that, to obtain another natural number, can only be divided by 1 or itself. A natural number is any whole positive number, e.g. 1, 2, 3... and so on. Non-prime numbers are called composite numbers and can be composed from 2 smaller natural numbers, called their factors. For example, 3 is a prime number as it can only be divided by 1 or 3 to obtain another natural number. The number 4 is not a prime number as it can be divided by 1 and itself, but also by 2. The number 4 can be composed from 2 smaller natural numbers: 2 * 2.

Methods

There are multiple methods to check if a number is prime, where often it is fastest to use a computer to do the calculations. There are an infinite amount of prime numbers and it is thus impossible to find all prime numbers that can theoretically exist. Hence, for some incomprehensibly big numbers it is still unknown whether they are prime or not, because it takes too long for the computer to do the calculations. The speed of the method depends on the size of the number to check and whether you want to be absolutely certain that the outcome is correct, or whether a good probability that the outcome is correct suffices.

Luckily, for most purposes, we can use fast algorithms that are, dependent on their exact implementation, deterministic, i.e., certain of the outcome. This calculator uses a deterministic trial division method and accepts any whole number above 0 and below one quadrillion (one quadrillion is 1000000000000000, a 1 with 15 zeroes). For even bigger numbers, the calculations become too heavy and you will have to rely on probabilistic tests, such as the Miller-Rabin Primality Test (Jaeschke, 1993). These probabilistic tests do not guarantee a correct outcome, although for most numbers just a small probability for failure.

Practical Applications of Prime Numbers

Prime numbers power some of the most important technologies everyone uses every day. Prime numbers especially play a central role in modern computing and cybersecurity, but also have their uses in biology, mechanical engineering, and even music.

Namely, one of the biggest real-world applications of prime numbers is encryption. Popular security systems like RSA encryption rely on the difficulty of factoring large prime numbers; usually with the Miller-Rabin procedure discussed in the previous section. Prime number based encryption algorithms are at work almost every time you shop online, log into a bank account, buy or sell cryptocurrency or send secure information over the internet.

Apart from encryption, computer science algorithms also benefit from prime numbers for hashing functions and (pseudo) random number generation. The Lehmer random number generator is one of those algorithms that utilizes prime numbers, for example (Payne, Rabung & Bogyo, 1969).

One of the weirder examples is that of cicadae, a type of bug. Many cicada species emerge on a cycle every 13 or 17 years — both of which are prime numbers (Yoshimura et al., 2009). During those years, billions of cicadas emerge simultaneously, mate, lay eggs, and die within weeks, almost exclusively on a prime number cycle. The leading evolutionary hypothesis for this phenomenon involves predator/competitor avoidance through mathematical unavoidability. Imagine a predator (or a competing cicada species) that also operates on a cycle - say, every 2, 3, 4, 5, or 6 years. If cicadas emerged on a non-prime schedule, their emergence would frequently coincide with predator population peaks, which is not beneficial. Namely, cycles coincide every LCM (least common multiple) years. If your cycle is prime, that LCM is almost always enormous. This example shows how prime numbers even "evolve" naturally and are an intrinsic (and useful) part of nature.