Prime Number Calculator

Q: What are the prime numbers from 1 to 100?

There are 25 primes from 1 to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Use the List mode of this calculator (enter limit = 100) to verify this instantly.

Q: What is a composite number?

A composite number is a positive integer greater than 1 that has at least one positive divisor other than 1 and itself. Examples: 4 = 2×2, 6 = 2×3, 9 = 3×3, 15 = 3×5. Every composite number can be expressed as a product of primes (its prime factorization). The Fundamental Theorem of Arithmetic guarantees this factorization is unique.

Q: What is the smallest prime factor?

The smallest prime factor of a composite number n is the smallest prime that divides n evenly. For even numbers it is always 2. For odd composites, you check 3, 5, 7, … up to √n. Example: smallest prime factor of 91 is 7, since 91 = 7 × 13. Knowing the smallest factor immediately confirms a number is composite.

Q: How many primes are there up to 1,000? Up to 10,000?

There are 168 primes up to 1,000 and 1,229 primes up to 10,000. The density of primes thins out as numbers grow — roughly 1 in ln(n) numbers near n is prime. This is the Prime Number Theorem: π(n) ≈ n / ln(n).

Q: What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an ancient algorithm to find all primes up to a limit N. Start with all integers from 2 to N marked as prime. For each prime p, cross out all multiples of p (starting from p²). Repeat until p > √N. The remaining marked numbers are all primes. It runs in O(N log log N) time and is very efficient for N up to a few million.

Check if a number is prime, find the next prime, or list all primes up to any limit.

#p What is a Prime Number?

A prime number is any integer greater than 1 that has exactly two positive divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The number 2 is the only even prime — every other even number is divisible by 2 and therefore composite. Numbers that are not prime (and not 1) are called composite numbers: they have at least one divisor between 1 and themselves.

Prime numbers are the fundamental building blocks of arithmetic. The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a unique product of primes (its prime factorization). For example, 360 = 2³ × 3² × 5. This uniqueness property makes primes central to number theory, cryptography (RSA encryption relies on the difficulty of factoring large numbers into primes), computer science, and pure mathematics.

Testing primality efficiently is a classic computer science problem. The simplest method — trial division — checks all integers from 2 to √n. This works well for numbers up to a few million. For enormous numbers (hundreds of digits), probabilistic tests like Miller–Rabin or deterministic algorithms like AKS are used. This calculator uses trial division, optimized to check only odd divisors after ruling out evenness, giving O(√n) performance.

To generate all primes up to a limit, the Sieve of Eratosthenes is the classical algorithm: mark all integers, then iteratively cross out multiples of each prime starting from 2. It runs in O(N log log N) time and is highly practical for N up to 10 million on modern hardware. This calculator's List mode uses this approach for limits up to 10,000.

📐 Formula & Rules

n is prime if n ≥ 2 and has no integer divisor d with 2 ≤ d ≤ √n

n = the integer to test

√n = square root of n — only need to check up to this value

Key fact: if n = a × b with a ≤ b, then a ≤ √n — so one factor is always at most √n

Example: Is 97 prime? √97 ≈ 9.85. Check 2, 3, 5, 7: none divide 97. 97 is prime.

Prime Counting: π(n) = number of primes ≤ n ≈ n / ln(n)

π(10) = 4 · π(100) = 25 · π(1,000) = 168 · π(10,000) = 1,229

The Prime Number Theorem shows primes become less dense as numbers grow.

📖 How to Use This Calculator

Check Prime Mode

Select Check Prime tab at the top of the calculator.

Enter the number you want to test (between 2 and 10,000,000).

Click Calculate to see: is it prime or composite, the next prime above it, the previous prime below it, and the smallest prime factor (for composite numbers).

List Primes Mode

Select List Primes tab.

Enter the upper limit (2 to 10,000). The calculator lists all primes up to that number.

Results show the total count of primes, the largest and smallest primes in the range, their sum, and the full list (up to 30 shown with a summary for larger sets).

💡 Example Calculations

Example 1 — Classic Prime: 97

Is 97 prime?

√97 ≈ 9.85, so check divisors 2, 3, 5, 7, 9

97 ÷ 2 = 48.5; 97 ÷ 3 = 32.3; 97 ÷ 5 = 19.4; 97 ÷ 7 = 13.86 — none are whole numbers

97 is prime. Next prime = 101. Previous prime = 89.

Try this example →

Example 2 — Composite: 91

Is 91 prime?

√91 ≈ 9.54. Check: 91 ÷ 7 = 13 exactly — divisible!

91 = 7 × 13. Smallest prime factor = 7.

91 is composite: 7 × 13. This often tricks people because it looks prime.

Try this example →

Example 3 — Large Prime: 999,983

Is 999,983 prime?

√999,983 ≈ 999.99. Trial division checks all odd numbers up to 999 — none divide it.

No divisors found — 999,983 has only the factors 1 and itself.

999,983 is prime. Previous prime = 999,979. Next prime = 1,000,003.

Try this example →

Example 4 — List All Primes Up to 50

Find all primes ≤ 50

Use List Primes mode, enter limit = 50.

Results: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

15 primes up to 50. Sum = 328. Largest = 47.

Try this example →

Frequently Asked Questions

What is a prime number?

A prime number is a natural number greater than 1 that has exactly two positive divisors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13. The number 2 is the only even prime; all other even numbers are divisible by 2 and therefore composite (having more than two divisors).

Is 1 a prime number?

No. 1 is not prime. By the modern definition, a prime must have exactly two distinct positive divisors (1 and itself). Since 1 has only one positive divisor, it is classified as neither prime nor composite. This definition ensures the Fundamental Theorem of Arithmetic works cleanly: every integer ≥ 2 has a unique prime factorization.

How do you check if a number is prime?

To check if n is prime: (1) If n < 2, not prime. (2) If n = 2, prime. (3) If n is even, not prime. (4) Check all odd numbers from 3 up to √n. If any divide n evenly, it is composite; otherwise it is prime. This works because if n has a factor larger than √n, it must also have one smaller than √n.

What are the prime numbers from 1 to 100?

There are 25 primes from 1 to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Use the List mode of this calculator (enter limit = 100) to verify this instantly.

What is a composite number?

A composite number is a positive integer greater than 1 that has at least one positive divisor other than 1 and itself. Examples: 4 = 2×2, 6 = 2×3, 9 = 3×3, 15 = 3×5. Every composite number can be expressed as a product of primes (its prime factorization). The Fundamental Theorem of Arithmetic guarantees this factorization is unique.

What is the smallest prime factor?

The smallest prime factor of a composite number n is the smallest prime that divides n evenly. For even numbers it is always 2. For odd composites, you check 3, 5, 7, … up to √n. Example: smallest prime factor of 91 is 7, since 91 = 7 × 13. Knowing the smallest factor immediately confirms a number is composite.

How many primes are there up to 1,000? Up to 10,000?

There are 168 primes up to 1,000 and 1,229 primes up to 10,000. The density of primes thins out as numbers grow — roughly 1 in ln(n) numbers near n is prime. This is the Prime Number Theorem: π(n) ≈ n / ln(n).

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an ancient algorithm to find all primes up to a limit N. Start with all integers from 2 to N marked as prime. For each prime p, cross out all multiples of p (starting from p²). Repeat until p > √N. The remaining marked numbers are all primes. It runs in O(N log log N) time and is very efficient for N up to a few million.

Are there infinitely many primes?

Yes. Euclid's proof (circa 300 BC): assume there are finitely many primes p1, p2, …, pk. Form Q = p1 × p2 × … × pk + 1. Q is either prime (contradiction) or has a prime factor not in our list (contradiction). Therefore the assumption was wrong, and primes are infinite. Modern research focuses on open problems like the twin prime conjecture and Goldbach's conjecture.

What are twin primes?

Twin primes are pairs of primes that differ by 2: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), and many more. The twin prime conjecture states there are infinitely many such pairs — it is unproven as of 2025. The largest known twin prime pair has over 388,000 digits.

Tags: Prime Number Calculator Is Prime Prime or Composite List of Primes Next Prime Prime Factor Sieve of Eratosthenes Calculator Number Theory Math Free

🔗 Related Calculators

📌 Quick Tips

💡2 is the only even prime number. All other even numbers are divisible by 2, making them composite.

💡1 is not prime by definition — a prime must have exactly two distinct positive divisors (1 and itself). The number 1 has only one positive divisor.

💡To test if n is prime by hand, you only need to check divisors up to √n. If no integer from 2 to √n divides n, then n is prime.

💡There are infinitely many prime numbers — Euclid proved this around 300 BC. The largest known prime (as of 2024) has over 41 million digits.

💡The prime counting function π(n) gives the number of primes ≤ n. For example, π(100) = 25: there are 25 primes up to 100.