Prime Number Checker

Mathematical Foundations of Prime Numbers

A prime number is a natural number strictly greater than 1 that cannot be formed by multiplying two smaller natural numbers. Prime numbers form the elementary building blocks of number theory, cryptography (including RSA public-key encryption and Diffie-Hellman key exchanges), and pseudorandom number generators.

Primality Testing Techniques

Testing whether a large integer $n$ is prime can be accomplished through deterministic or probabilistic algorithms:

Method	Time Complexity	Determinism	Application
Trial Division	$O(\sqrt{n})$	Deterministic	Small integers ($n < 10^{12}$)
Sieve of Eratosthenes	$O(n \log \log n)$	Deterministic	Generating all primes up to $n$
Fermat Primality Test	$O(k \log^2 n)$	Probabilistic	Rapid screening (vulnerable to Carmichael numbers)
Miller-Rabin Test	$O(k \log^3 n)$	Probabilistic / Deterministic for $n < 3.317 \times 10^{24}$	Cryptography and large integer validation

---

Optimised Trial Division Algorithm

When testing a number $n$ using trial division, one does not need to check all integers up to $n$ or even $n/2$. Any composite number $n$ must have at least one prime factor $p \le \sqrt{n}$. Furthermore, all primes greater than 3 can be expressed in the form $6k \pm 1$:

1. Eliminate numbers $\le 1$.
2. Check divisibility by 2 and 3.
3. Test divisors of the form $6k - 1$ and $6k + 1$ up to $\sqrt{n}$.

---

Primality Testing in Code

JavaScript

function isPrime(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;
}

Python

def is_prime(n: int) -> bool:
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True