Prime Number Calculator

Check if a number is prime, list primes in a range, and explore how prime and composite numbers behave in number theory and cryptography.

Check If a Number Is Prime

Result -

List Primes in a Range

Primes -

Prime Numbers: Definitions, Tests, and Uses

Prime numbers are the building blocks of whole numbers and play a central role in number theory, cryptography, and algorithms.

This guide follows the same structure as your other calculator pages, with clear boxes, examples, tables, pitfalls, and practice problems focused on primes and composites.

What Is a Prime Number?

A prime number is a natural number greater than 1 that has exactly two positive divisors: 1 and itself.

Basic definitions
  • Prime number: Has only 1 and itself as factors (e.g., 2, 3, 5, 7, 11).
  • Composite number: Has at least one additional factor besides 1 and itself (e.g., 4, 6, 8, 9, 10).
  • Special cases: 0 and 1 are neither prime nor composite.
Number Type Factors
2 Prime 1, 2
7 Prime 1, 7
9 Composite 1, 3, 9
12 Composite 1, 2, 3, 4, 6, 12
1 Neither 1
Example:
13 is prime because only 1 and 13 divide it without remainder; 15 is composite because it has factors 1, 3, 5, 15.

Prime Testing: How to Check If a Number Is Prime

To test primality efficiently, you do not need to try dividing by all smaller numbers, only by primes up to the square root.

Trial division test

For n > 1, n is prime if it is not divisible by any integer from 2 to ⌊√n⌋.

Example 1: Is 29 prime?
√29 is a little more than 5; test divisibility by 2, 3, 5.
29 ÷ 2, 3, 5 are not integers, so 29 is prime.
Example 2: Is 77 prime?
√77 is less than 9; test 2, 3, 5, 7.
77 ÷ 7 = 11, so 77 is composite.
n √n (approx) Divisors to test Conclusion
31 5.56 2, 3, 5 Prime
45 6.70 2, 3, 5, 6 Composite (3, 5)
97 9.85 2 … 9 Prime

Prime Factorization and Fundamental Theorem of Arithmetic

Every composite number can be written uniquely as a product of prime numbers, ignoring order.

Prime factorization

Prime factorization expresses a number as a product of primes, like 60 = 2² × 3 × 5.

Example 1: Factor 84
84 = 2 × 42 = 2 × 2 × 21 = 2² × 3 × 7.
Example 2: Factor 90
90 = 9 × 10 = 3² × 2 × 5 = 2 × 3² × 5.
Number Prime Factorization Prime?
19 19 Yes
28 2² × 7 No
45 3² × 5 No
101 101 Yes

Where Prime Numbers Are Used

Primes appear naturally in mathematics and are crucial in modern security systems, hashing, and algorithm design.

🔐 Cryptography

Large primes are used in public‑key cryptosystems (like RSA) to secure data and communications.

🧮 Number Theory

Primes are central in the study of divisibility, modular arithmetic, and advanced theorems about integers.

💻 Hashing and Randomness

Primes help design hash functions, random number generators, and data structures like hash tables.

📐 Geometry and Patterns

Prime‑based structures appear in tilings, combinatorics, and patterns in Pascal’s triangle.

📊 Error‑Correcting Codes

Finite fields built using primes are used in coding theory for reliable data transmission.

🎮 Competitive Programming

Prime sieves and modular arithmetic are standard tools in algorithmic problem solving.

Common Mistakes About Primes

Many errors come from misclassifying special numbers or using inefficient prime tests without limits.

❌ MISTAKE 1: Calling 1 a prime number
1 has only one positive divisor (itself), not two distinct divisors.
✅ Primes must have exactly two distinct positive divisors: 1 and the number itself.
❌ MISTAKE 2: Forgetting that 2 is prime
2 is the only even prime, and every other even number is composite.
✅ Always treat 2 as a prime when building prime lists or sieves.
❌ MISTAKE 3: Testing all numbers up to n
Dividing all the way to n is slow and unnecessary for larger inputs.
✅ Only test divisors up to √n, and preferably only prime candidates (2 and odd numbers).
❌ MISTAKE 4: Overflow in large ranges
Generating primes in very large ranges without limits can freeze browsers or scripts.
✅ Use reasonable upper bounds or efficient sieves with complexity in mind.

Prime Patterns and Interesting Facts

Although primes look random, they follow deep patterns studied in advanced mathematics.

Basic observations
  • Except for 2 and 3, all primes are of the form 6k ± 1.
  • There are infinitely many primes (proved by Euclid).
  • Twin primes are pairs like (3, 5), (5, 7), (11, 13) that differ by 2.
Prime Pair Type Details
(2, 3) Consecutive primes Only neighboring primes
(3, 5) Twin primes Difference of 2
(11, 13) Twin primes Difference of 2
(17, 19) Twin primes Difference of 2

Practice Problems with Solutions

Try these prime and composite questions, then verify quickly using the Prime Number Calculator above.

Basic Level
Problem 1: Determine whether 23, 35, and 37 are prime or composite.
Show Solution

23: Test divisors 2, 3, 4; none divide → prime.
35: 35 = 5 × 7 → composite.
37: Test 2, 3, 5; none divide → prime.

Problem 2: List all primes between 10 and 30.
Show Solution

11, 13, 17, 19, 23, 29.

Intermediate Level
Problem 3: Find the prime factorization of 72.
Show Solution

72 = 8 × 9 = 2³ × 3².

Problem 4: Without fully factoring, show that 221 is composite.
Show Solution

√221 ≈ 14.8; test primes 2, 3, 5, 7, 11, 13.
221 ÷ 13 = 17, so 221 = 13 × 17 → composite.

Advanced Level
Problem 5: Show that every composite number up to 50 has a prime factor ≤ 7, and give an example for each prime 2, 3, 5, 7.
Show Solution

√50 ≈ 7.07, so any composite ≤ 50 has a factor ≤ 7.
Examples: 2 | 14, 3 | 27, 5 | 35, 7 | 49.

Problem 6: Between 90 and 110, find all primes and verify using the calculator.
Show Solution

Candidates: 97, 101, 103, 107, 109.
Each passes divisibility tests up to √n → primes are 97, 101, 103, 107, 109.