Prime Number Calculator
number
Result
3 is prime!
Its only factors are 1 and 3
More calculators
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.
Prime numbers have practical applications in many fields such as computer-science, finance and even music.
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.
References
- Jaeschke, G. (1993). On strong pseudoprimes to several bases. Mathematics of Computation, 61(204), 915-926.