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.

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!

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).

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 that do not exceed √n. A version of the trial division algorithm powers this prime number calculator.

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:

1. Write down all numbers from 2 to n.

2. 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).

3. Take the smallest number that is not circled or crossed out: 3. Circle it and cross out all its further multiples: 3, 6, 9, ....

4. Continue in the same way: find the smallest available number, p, circle it, and cross out all of its consecutive multiples.

5. 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 three-quarters of a year) to write this number down in its entirety, provided that one digit per second is being written down!

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, for example:

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.

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:

1. 18 and 30 are not relatively prime, as they are both divisible by 3. You may also note that their GCD is 6.

2. 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.

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!