# Prime Number Calculator

With 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 number preceding 7 (2, 3, 4, 5, and 6) is a factor of it, because none of these numbers divide 7 without a remainder.
- 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 amongst 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 non-trivial factor (non-trivial 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 so-called **trial division** algorithm: it consists of testing whether `n`

is divisible by any number between `2`

and `n-1`

. 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 which 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`

to`n`

- Start with the smallest number in our list:
`2`

. Circle`2`

and cross out all consecutive multiples of`2`

(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 this 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`

not yet crossed out. If so, repeat Step 4. If no, 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`

- the remaining purple numbers are prime

Sieve of Eratosthenes (by SKopp - Own work, CC BY-SA 3.0, wikimedia.org)

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 on-going: 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 three-quarters 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 **fundamental theorem of arithmetic**: *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 our prime factorization calculator.

Actually, 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, e.g.,

`6 = 2 * 3 = 1 * 2 * 3 = 1 * 1 * 2 * 3 = ...`

As for real-life applications of prime numbers, you may encounter them, e.g., in cryptography protocols, such as the well-known RSA encryption.

## 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 Divisor (GCD) is equal to 1.

For instance:

`18`

and`30`

are not relatively prime, as they are both divisible by`3`

. You may also note that their GCD is`6`

.`18`

and`35`

are relatively prime: the factors of`18`

read`1, 2, 3, 6, 9, 18`

and that of`35`

read`1, 5, 7, 35`

. We see that the sole common divisor of`18`

and`35`

is`1`

.

Remember:

- Two primes are always relatively prime
- But numbers need not be prime in order to be relatively prime!