Prime Number Checker

Check if a number is prime and list its factors if composite.

Reviewed by the ToolNestr Editorial Team — July 2026

Check number Generate primes up to N

Enter number

How prime number checking works

This tool uses trial division — the simplest and most intuitive primality test. A number n is checked by testing divisibility against every integer from 2 up to the square root of n (√n). If any of these divides n evenly, then n is composite. If none divide evenly, then n is prime. The algorithm is optimised by treating 2 as a special case and then only testing odd divisors, which cuts the work in half.

For factor listing, once a divisor is found, the tool divides n by that divisor to get the complementary factor, ensuring all factors are identified. Factors are collected in order and duplicates are removed when the divisor and quotient are the same (perfect squares).

For prime generation, the tool applies the same trial-division check to every number from 2 up to the specified limit. While the Sieve of Eratosthenes is faster for generating many primes, trial division is used here so that the generation logic is consistent with the checker logic and works efficiently for moderate limits.

Worked example: checking 97

√97 ≈ 9.8, so we test divisors up to 9.

97 ÷ 2 = 48.5 → not a whole number ✗

97 ÷ 3 = 32.33 → not a whole number ✗

97 ÷ 5 = 19.4 → not a whole number ✗

97 ÷ 7 = 13.857 → not a whole number ✗

97 ÷ 9 = 10.777 → not a whole number ✗

No divisor found → 97 is PRIME ✓

Number line with primes highlighted

Primes are marked in green on the number line below. Notice how primes become less frequent as numbers get larger.

📚

Math Homework

Quickly check if numbers are prime for homework assignments on number theory, divisibility, or prime factorisation.

🔒

Cryptography Learning

Understand the foundational building blocks of RSA and other encryption algorithms that rely on the difficulty of factoring large semiprimes.

🏫

Teaching Number Theory

Demonstrate primality testing and factorisation in the classroom with instant feedback and clear visual results.

🧮

Competitive Programming

Verify edge cases and generate primes quickly while practising algorithmic problem-solving with number theory problems.

Tips for working with primes

Even numbers greater than 2 are never prime

Any even number can be divided by 2, so it has at least three factors (1, 2, and itself). This is why the trial division algorithm skips all even divisors after checking 2.

Use the Sieve of Eratosthenes for large ranges

To generate all primes up to a large limit (say, 10 million), the Sieve of Eratosthenes is far more efficient than trial division. The sieve works by marking multiples of each prime starting from 2, leaving only the unmarked numbers as primes.

Only check divisors up to the square root

If n has a factor greater than √n, it must have a complementary factor smaller than √n. So checking only up to √n is sufficient to determine primality.

Watch for perfect squares

When listing factors of a perfect square (like 16 or 36), include the square root only once. For example, factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36 — notice 6 appears only once.

What is a prime number?

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. This means it cannot be formed by multiplying two smaller natural numbers. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. The number 2 is the only even prime — all other even numbers are divisible by 2 and therefore composite.

Prime numbers are the fundamental building blocks of arithmetic. The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed uniquely as a product of primes (up to ordering). This unique factorisation property is what makes primes so important in number theory and cryptography.

Trial division algorithm

The algorithm used in this tool is straightforward:
1. If n ≤ 1, it is not prime.
2. If n is 2, it is prime (special case for the only even prime).
3. If n is even (divisible by 2), it is composite.
4. Check divisibility by every odd number from 3 up to √n.
5. If any divisor is found, n is composite; otherwise it is prime.

For factor listing, step 4 collects both the divisor and the quotient (n / divisor) as factors, then sorts them in ascending order. This ensures all factors are captured efficiently in a single pass.

History of prime numbers

The study of prime numbers dates back to ancient Greece. Euclid's Elements (circa 300 BC) contains the first known proof that there are infinitely many primes. Euclid's proof assumes a finite list of primes and constructs a new number that must have a prime factor not on the list, creating a contradiction.

Eratosthenes of Cyrene (circa 240 BC) developed the Sieve of Eratosthenes, still the most efficient way to generate all small primes. In the 17th century, Pierre de Fermat made important contributions, including Fermat's Little Theorem, which is the basis for many modern primality tests. Marin Mersenne studied primes of the form 2^p − 1, now called Mersenne primes, which are the source of the largest known primes today.

In the 20th century, the search for large primes transitioned from manual calculation to computers. The Great Internet Mersenne Prime Search (GIMPS), founded in 1996, has discovered all recent record primes by harnessing distributed computing power from thousands of volunteers worldwide.

Primes in cryptography

Prime numbers are the backbone of modern public-key cryptography. The RSA algorithm, published in 1977 by Rivest, Shamir, and Adleman, generates two large primes (typically hundreds of digits long), multiplies them together, and uses the product as part of the public key. The security of RSA relies on the fact that factoring the product back into its original primes is computationally infeasible with current technology.

Other cryptographic systems that rely on primes include Diffie-Hellman key exchange, DSA (Digital Signature Algorithm), and elliptic-curve cryptography. The practical upshot is that whenever you visit a secure website (HTTPS), send an encrypted message, or sign a digital document, prime numbers are working behind the scenes to protect your data.