Prime Number Calculator
Table of contents
What is a prime number?How to use our prime number calculatorHow to check if a number is prime or compositeHow to find prime numbersWhy do prime numbers matter?Relatively prime numbersWith our prime number calculator you can check if any given number is prime or composite.
Keep reading if you want to learn what a prime number is, and how to check if a number is prime. We also discuss how to find prime numbers, as well as what relatively prime numbers are. As a bonus, we tell you if 1 is prime, and also what the oddest prime number is.
What is a prime number?
A natural number greater than 1 is called prime if it has exactly two factors, i.e., if the number is divisible only by 1 and itself.
When a natural number is greater than 1 and isn't prime, then it's called a composite number.
What about 1? 1 is neither prime nor composite as it has only one factor (itself).
Let's discuss some examples:
 7 is prime because its only factors are 1 and 7. Indeed, none of the numbers preceding 7 (2, 3, 4, 5, and 6) is a factor of it because none of these numbers divide 7 without a remainder. If you don't quite remember what that means, go to the remainder calculator.
 8 is composite because 2 is a factor of 8, and so 8 has more factors than just 1 and 8.
Fun fact. The oddest number among primes is 2, as it is the only even prime; all other primes are odd!
How to use our prime number calculator
Well, this prime number calculator is not a very complicated one. Just enter the number you wish to check into the calculator, and voila! Your answer will be shown below.
If your number is composite, the calculator will tell you its smallest nontrivial factor (nontrivial here means a factor greater than one).
How to check if a number is prime or composite
The easiest way to verify that a given integer n is prime is to apply the socalled trial division algorithm: it consists of testing whether n is divisible by any number between 2 and n1. That's a lot of computations. Fortunately, the number of trials can be reduced; it is sufficient to check only the divisibility of n by prime numbers that do not exceed √n. A version of the trial division algorithm powers this prime number calculator.
How to find prime numbers
Well, you cannot find every prime number because Euclid proved sometime around 300 BC that there are an infinite number of them.
If you want to find all prime numbers up to some given limit, n
, you may resort to the algorithm known as the Sieve of Eratosthenes:

Write down all numbers from
2
ton
. 
Start with the smallest number in our list:
2
. Circle2
and cross out all consecutive multiples of2
(i.e.,4, 6, 8, ..., 120
). 
Take the smallest number that is not circled or crossed out:
3
. Circle it and cross out all its further multiples:3, 6, 9, ...
. 
Continue in the same way: find the smallest available number,
p
, circle it, and cross out all of its consecutive multiples. 
Check if there are numbers greater than
p
that have not yet been crossed out. If so, repeat Step 4. If not, we're done.
The circled numbers in the list are all the primes below n
.
The main idea here is that every number assigned to p
in any step of the algorithm is necessarily prime; otherwise, it would be crossed out as a multiple of some smaller, already circled prime number.
In the animation below, you see the Sieve of Eratosthenes searching for all primes up to 120
.
Here's the color legend:
 Red: multiples of
2
;  Green: multiples of
3
;  Blue: multiples of
5
;  Yellow: multiples of
7
; and  The remaining purple numbers are prime.
As you may imagine, for REALLY BIG numbers, it is quite challenging to decide whether they are prime or composite, and therefore, very elaborate methods are required. The search for big primes is ongoing: as of March 2020, the largest known prime number has 24,862,048
digits! Our time unit converter helps us estimate that it would take roughly 288
days (so more than threequarters of a year) to write this number down in its entirety, provided that one digit per second is being written down!
Why do prime numbers matter?
Prime numbers are crucial in number theory because of the prime factorization calculator.
: every natural number greater than 1 can be written as a product of primes in a unique way (up to the order of multiplication). In other words, primes can be thought of as the building blocks of all other natural numbers. To learn more about prime factorization, check ourActually, this theorem is one of the main reasons why we don't want 1
to be called a prime number.
If 1
were prime, then prime factorization would no longer be unique because we would have, for example:
6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 = ...
As for reallife applications of prime numbers, you may encounter them, e.g., in cryptography protocols, such as the wellknown
.Relatively prime numbers
Do not confuse the notion of prime numbers with that of relatively prime numbers! Two natural numbers are called relatively prime (or coprime) if there is no integer other than 1 that divides both these numbers. In other words, their greatest common factor (GCF) is equal to 1.
For instance:

18
and30
are not relatively prime, as they are both divisible by3
. You may also note that their GCD is6
. 
18
and35
are relatively prime: the factors of18
read1, 2, 3, 6, 9, 18
and that of35
read1, 5, 7, 35
. We see that the sole common divisor of18
and35
is1
.
To learn more, visit the GCF calculator.
Remember:
 Two primes are always relatively prime
 But numbers need not be prime in order to be relatively prime!