Prime Number Checker

About Prime Number Checker

This prime number checker determines whether a positive integer is prime using trial division up to √n. For each input, it checks divisibility by integers from 2 to the square root of the number. If no divisor is found, the number is prime. The tool also displays prime factorization for composite numbers.

It is useful for mathematics education, number theory exercises, cryptography applications, verifying prime factors, and exploring properties of prime and composite numbers.

Prime Number Definition

A prime number is a natural number greater than 1 with exactly two positive divisors:

Prime Numbers:
  - Greater than 1
  - Divisible only by 1 and itself
  - Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Not Prime:
  - 1 is neither prime nor composite
  - 0 is not prime (has infinite divisors)
  - Negative numbers are not prime
  - Composite numbers have more than 2 divisors

First 25 Prime Numbers:
  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

Prime Count by Range:
  1-100:    25 primes
  1-500:    95 primes
  1-1000:   168 primes
  1-10000:  1229 primes
  1-100000: 9592 primes

Primality Testing Algorithms

Trial Division Method

Trial Division Algorithm:

1. If n < 2: not prime
2. If n = 2: prime (only even prime)
3. If n is even: not prime
4. Check odd divisors from 3 to √n:
   - If n % i == 0: not prime
   - If no divisor found: prime

Optimization (6k ± 1 rule):
  All primes > 3 are of form 6k±1
  Check divisibility by 2 and 3 first
  Then check 5, 7, 11, 13, 17, 19...
  (skip multiples of 2 and 3)

JavaScript Implementation:
  function isPrime(n) {
    if (n < 2) return false;
    if (n === 2) return true;
    if (n % 2 === 0) return false;

    const sqrt = Math.floor(Math.sqrt(n));
    for (let i = 3; i <= sqrt; i += 2) {
      if (n % i === 0) return false;
    }
    return true;
  }

Optimized Implementation:
  function isPrimeOptimized(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;

    for (let i = 5; i * i <= n; i += 6) {
      if (n % i === 0 || n % (i + 2) === 0) {
        return false;
      }
    }
    return true;
  }

Example: Check if 97 is prime
  √97 ≈ 9.85
  Check divisors: 2, 3, 5, 7, 9
  97 % 2 = 1 ✓
  97 % 3 = 1 ✓
  97 % 5 = 2 ✓
  97 % 7 = 6 ✓
  97 % 9 = 7 ✓
  Result: 97 is prime!

Prime Factorization

Prime Factorization Algorithm:

1. Start with smallest prime (2)
2. Divide n by prime while divisible
3. Move to next prime
4. Repeat until n = 1

Example: Factorize 360
  360 ÷ 2 = 180
  180 ÷ 2 = 90
  90 ÷ 2 = 45
  45 ÷ 3 = 15
  15 ÷ 3 = 5
  5 ÷ 5 = 1

  Result: 360 = 2³ × 3² × 5

Example: Factorize 84
  84 ÷ 2 = 42
  42 ÷ 2 = 21
  21 ÷ 3 = 7
  7 ÷ 7 = 1

  Result: 84 = 2² × 3 × 7

JavaScript Implementation:
  function primeFactorize(n) {
    const factors = {};
    let divisor = 2;

    while (n > 1) {
      while (n % divisor === 0) {
        factors[divisor] = (factors[divisor] || 0) + 1;
        n /= divisor;
      }
      divisor++;
      if (divisor * divisor > n) {
        if (n > 1) {
          factors[n] = (factors[n] || 0) + 1;
          break;
        }
      }
    }
    return factors;
  }

Special Prime Categories

Code Examples by Language

JavaScript:
  // Basic trial division
  function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i * i <= n; i++) {
      if (n % i === 0) return false;
    }
    return true;
  }

Python:
  def is_prime(n):
      if n < 2:
          return False
      for i in range(2, int(n**0.5) + 1):
          if n % i == 0:
              return False
      return True

  # Using sympy library
  from sympy import isprime
  isprime(97)  # True

PHP:
  function isPrime($n) {
      if ($n < 2) return false;
      for ($i = 2; $i * $i <= $n; $i++) {
          if ($n % $i === 0) return false;
      }
      return true;
  }

Java:
  public static boolean isPrime(int n) {
      if (n < 2) return false;
      for (int i = 2; i * i <= n; i++) {
          if (n % i == 0) return false;
      }
      return true;
  }

C++:
  bool isPrime(int n) {
      if (n < 2) return false;
      for (int i = 2; i * i <= n; i++) {
          if (n % i == 0) return false;
      }
      return true;
  }

Bash:
  is_prime() {
      local n=$1
      if [ $n -lt 2 ]; then return 1; fi
      local i=2
      while [ $((i * i)) -le $n ]; do
          if [ $((n % i)) -eq 0 ]; then return 1; fi
          ((i++))
      done
      return 0
  }

Prime Number Examples

Small Primes:
  2  - Only even prime
  3  - First odd prime
  5  - Divisible only by 1, 5
  7  - Lucky number
  11 - Palindromic prime

Two-Digit Primes:
  13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
  53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Large Primes:
  101  - First 3-digit prime
  1009 - First 4-digit prime
  9973 - Largest 4-digit prime

Composite Examples:
  4  = 2²
  6  = 2 × 3
  12 = 2² × 3
  30 = 2 × 3 × 5
  60 = 2² × 3 × 5
  100 = 2² × 5²

Special Cases:
  1  - Neither prime nor composite
  0  - Not prime (infinite divisors)
  -5 - Not prime (negative)
  2.5 - Not prime (not an integer)

Mathematical Properties

Fundamental Theorem of Arithmetic:
  Every integer > 1 is either prime or can be
  uniquely represented as a product of primes.

  Example: 60 = 2² × 3 × 5 (unique factorization)

Prime Number Theorem:
  The number of primes ≤ n is approximately n/ln(n).

  For n = 1000:
  Actual: 168 primes
  Approx: 1000/ln(1000) ≈ 145 primes

  As n → ∞, the approximation becomes exact.

Goldbach's Conjecture (Unproven):
  Every even integer > 2 can be expressed as
  the sum of two primes.

  Examples:
  4 = 2 + 2
  10 = 3 + 7 = 5 + 5
  100 = 3 + 97 = 11 + 89 = 17 + 83

Euclid's Theorem:
  There are infinitely many prime numbers.

  Proof (by contradiction):
  Assume finite primes: p₁, p₂, ..., pₙ
  Let N = p₁ × p₂ × ... × pₙ + 1
  N is not divisible by any pᵢ
  Therefore N is prime or has a new prime factor
  Contradiction! → Infinitely many primes

Wilson's Theorem:
  (p-1)! ≡ -1 (mod p) if and only if p is prime.

  Example for p = 5:
  4! = 24
  24 mod 5 = 4 = -1 (mod 5) ✓

Applications of Prime Numbers

Best Practices

• Use optimized algorithms: For large numbers, use Miller-Rabin or AKS instead of simple trial division.
• Consider number size: Trial division works for small numbers; cryptographic primes need specialized libraries.
• Verify with multiple methods: For critical applications, cross-check results with different algorithms.
• Understand limitations: Browser JavaScript has integer precision limits (~2^53).
• Use appropriate libraries: For cryptographic applications, use established crypto libraries.

Limitations

• Integer precision: JavaScript Number type limits accuracy to ~2^53 (9 × 10^15).
• Performance: Trial division becomes slow for very large numbers (> 10^12).
• No probabilistic testing: Does not implement Miller-Rabin or other probabilistic methods.
• Single number only: Checks one number at a time; no batch processing.
• No primality proof: Does not generate mathematical proof of primality.