CALTRX

Prime Number Checker

Determine if any number is prime and see its factors. See the complete solution with step-by-step working and formula explanations.

Enter your values above to see the results.

Tips & Notes

  • ✓Only test divisors up to √n. For n=1000, test only up to 31.6 — massive speedup over testing all numbers.
  • ✓Every even number > 2 is composite. Check divisibility by 2 first — eliminates half of all candidates instantly.
  • ✓Divisibility by 3: sum the digits. If sum divisible by 3, so is n. 123: 1+2+3=6 → divisible by 3.
  • ✓Numbers ending in 5 (other than 5 itself) are always divisible by 5 and therefore composite.
  • ✓Factors count = (a+1)(b+1)... for n=pᵃqᵇ. For 1000=2³×5³: (3+1)(3+1) = 16 factors.

Common Mistakes

  • ✗1 is NOT prime. Primes have exactly 2 distinct divisors. 1 has only one divisor — itself.
  • ✗Assuming large odd numbers are prime without testing. 91=7×13, 119=7×17, 143=11×13 all look prime but are not.
  • ✗Testing only odd divisors and skipping 2. Always check 2 first for any even number.
  • ✗Confusing prime with odd. All primes >2 are odd, but NOT all odd numbers are prime: 9,15,21,25,27 are composite.
  • ✗Stopping factorization at composite factors. 12=4×3 is incomplete because 4=2². Full form: 2²×3.

Prime Number Checker Overview

A prime number has exactly two distinct positive divisors: 1 and itself. Every integer greater than 1 is either prime or composite — the Fundamental Theorem of Arithmetic guarantees this, and the unique prime factorization of every composite number into primes is the cornerstone of number theory and modern cryptography.

The primality test — trial division method:

To test if n is prime: check divisibility by every integer from 2 to √n. If none divide evenly, n is prime.
EX: Is 97 prime? √97 ≈ 9.85. Test: 97÷2=48.5✗ 97÷3=32.3✗ 97÷5=19.4✗ 97÷7=13.9✗ No divisor found → 97 is prime ✓
Why we only test up to √n:
If n has a factor greater than √n, it must also have a factor smaller than √n — so testing up to √n is sufficient
EX: Is 91 prime? √91 ≈ 9.54. Test: 91÷7=13 exactly → 91=7×13 → 91 is composite. Note: 7 < √91 and 13 > √91 — finding 7 was sufficient.
The prime number theorem describes how primes thin out as numbers grow larger. The number of primes up to n is approximately n/ln(n). Near 1,000, about 1 in 7 numbers is prime. Near 1,000,000, about 1 in 14. Near 10⁹, about 1 in 21. Despite this thinning, Euclid proved around 300 BCE that primes never stop — the sequence continues infinitely, a proof elegant enough to appear in every introduction to mathematical reasoning. The distribution of prime numbers among all integers follows a pattern that becomes statistically predictable at large scales despite being locally unpredictable at small scales. This apparent randomness in a deterministic system makes large primes ideal for cryptographic keys — an attacker cannot predict which large numbers are prime without testing each candidate, which requires significant computation for numbers with hundreds of digits.

Frequently Asked Questions

A prime number has exactly two distinct positive factors: 1 and itself. 17 is prime (factors: 1, 17 only). 15 is not prime (factors: 1, 3, 5, 15 — four factors). To check if n is prime: test divisibility by all integers from 2 to √n. If none divide evenly, n is prime. Example: is 97 prime? √97 ≈ 9.85. Test 2, 3, 5, 7 (no need to test 9 since 3 already checked). None divide 97 evenly → 97 is prime. You never need to test beyond √n.

The Sieve of Eratosthenes finds all primes up to n efficiently. Start with a list of integers 2 to n. Mark 2 as prime, cross out all multiples of 2. Find next unmarked number (3), mark as prime, cross out multiples of 3. Continue until you reach √n — everything unmarked is prime. For n=100: cross out multiples of 2, 3, 5, 7 (primes ≤ √100=10). Remaining unmarked: 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 — exactly 25 primes.

There are infinitely many primes — proved by Euclid around 300 BCE. Proof: assume there are finitely many primes p₁, p₂, ..., pₙ. Consider N = (p₁×p₂×...×pₙ) + 1. N is either prime (contradiction — it is not in the list) or has a prime factor not in the list (also a contradiction). Therefore the assumption of finitely many primes is false. Primes become less frequent as numbers grow, but they never stop entirely — the prime number theorem shows density near n is approximately 1/ln(n).

The largest known prime (as of 2024) is 2^136,279,841 − 1 (a Mersenne prime), discovered in October 2024. It has 41,024,320 digits. Mersenne primes have the form 2^p − 1 where p itself must be prime. The Great Internet Mersenne Prime Search (GIMPS) uses distributed computing to find new Mersenne primes. RSA-2048 encryption uses a different 617-digit prime — impossibly small compared to these mathematical giants, but computationally unbreakable for factoring purposes.

The Goldbach conjecture (1742, still unproven): every even integer greater than 2 is the sum of two primes. Verified for all even numbers up to 4×10¹⁸. Examples: 4=2+2, 6=3+3, 28=5+23=11+17, 100=3+97=11+89=29+71. The Twin Prime conjecture: there are infinitely many pairs of primes differing by 2 (3&5, 11&13, 17&19, 41&43). Both conjectures are widely believed true but neither has been proved — they remain among mathematics' most famous open problems.

RSA encryption, the foundation of most internet security, relies on one mathematical fact: multiplying two large prime numbers together takes milliseconds, but factoring the result back into those two primes is computationally infeasible at large scales. A modern RSA key uses primes with 1024-2048 bits each (roughly 300-600 decimal digits). Their product — the public key — can be shared openly. Encrypting a message uses the public key; decrypting requires knowing the prime factors (the private key). An attacker who only has the product cannot recover the primes in any reasonable time with known algorithms. This security relies entirely on the hardness of prime factorization for large numbers.