Prime Number Calculator — Check Primality & Find Factors

The Formula

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. To check primality, we use trial division: test whether n is divisible by any integer from 2 up to the square root of n. If none divide evenly, n is prime. This method works because if n has a divisor d greater than sqrt(n), then n/d would be a divisor smaller than sqrt(n), so we only need to check up to sqrt(n).

Variable Definitions

How to Use This Calculator

1. 1

   Enter any positive integer between 1 and 10,000,000 in the input field.

2. 2

   The calculator instantly tells you whether the number is prime or composite.

3. 3

   If the number is composite, view its complete list of prime factors separated by commas.

4. 4

   See the divisor count to understand how many numbers divide the input evenly.

5. 5

   Read the step-by-step primality check to understand exactly how the determination was made.

Quick Reference

Common Applications

• Cryptography: RSA encryption relies on the difficulty of factoring large composite numbers into primes.
• Number theory research: understanding the distribution of primes (e.g., the Prime Number Theorem).
• Computer science: primality testing algorithms are fundamental to algorithmic number theory.
• Educational: learning about divisibility, factors, and the building blocks of the number system.
• Mathematics competitions: many contest problems involve prime numbers and factorization.

Prime number distribution from 1 to 100. Primes are shown in green. There are 25 primes in the first 100 numbers, illustrating that primes become sparser as numbers increase.

Understanding the Concept

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In other words, a prime has exactly two distinct divisors: 1 and itself. The number 2 is the smallest prime and the only even prime — every other even number is divisible by 2. The primes below 20 are 2, 3, 5, 7, 11, 13, 17, and 19. There are infinitely many primes, a fact proven by Euclid around 300 BCE using a clever argument: if you have any finite list of primes, multiply them together, add 1, and the result is either a new prime or has a prime factor not in your original list. Primes become less frequent as numbers grow larger, but there is no largest prime. Trial division is the simplest primality test: check whether n is divisible by any integer from 2 up to sqrt(n). If none divide evenly, n is prime. This is efficient for numbers up to 10 million because we only check up to sqrt(n), which for 10 million is about 3162. For larger numbers, more sophisticated tests like the Miller-Rabin test are used. The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be uniquely expressed as a product of primes — making primes the building blocks of all integers. This is why prime factorization (breaking a number into its prime factors) is such an important tool.

Frequently Asked Questions

Sources & References