Check if a number is prime and find all primes within a range
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. 2, 3, 5, 7, 11, 13, 17, 19, 23... are the first primes. 4 is not prime (4 = 2×2). 1 is not prime by convention (it has only one divisor). The fundamental theorem of arithmetic states that every integer greater than 1 can be expressed uniquely as a product of prime numbers — primes are the "atoms" of multiplication.
This tool checks whether a number is prime, finds its prime factorisation if composite, and lists primes in a given range. For primality testing, it uses efficient algorithms: trial division for small numbers, Miller-Rabin probabilistic primality test for larger numbers. Prime numbers underpin modern cryptography — RSA encryption relies on the difficulty of factoring large numbers into their prime components.
For small numbers (<10⁶): trial division up to √n is sufficient. For medium numbers (10⁶–10¹⁵): deterministic Miller-Rabin with specific witnesses guarantees correctness. For very large numbers (cryptographic, 10⁵⁰⁰+): probabilistic Miller-Rabin with multiple rounds gives overwhelming probability of correctness, supplemented by Lucas primality tests. The fastest known general algorithm is AKS (Agrawal–Kayal–Saxena), proven polynomial-time in 2002.
Yes. Euclid proved this around 300 BC with an elegant argument: assume a finite list of primes P₁, P₂, ..., Pₙ. Multiply them all and add 1: N = P₁×P₂×...×Pₙ + 1. This number is either prime (a new prime not in the list) or divisible by a prime not in the list. Either way, the list was incomplete — contradiction. Therefore there are infinitely many primes.
The Sieve of Eratosthenes is an ancient algorithm for finding all primes up to a limit n. Algorithm: (1) Create a boolean array of size n+1, all true. (2) Starting from p=2, mark all multiples of p (p², p²+p, p²+2p, ...) as false. (3) Find the next unmarked number and repeat. (4) All remaining true entries are prime. Time complexity: O(n log log n). For finding all primes up to 10⁷, this fits in memory and runs in milliseconds.
A Mersenne prime is a prime of the form 2ⁿ − 1. Examples: 2²-1=3, 2³-1=7, 2⁵-1=31, 2⁷-1=127, 2¹³-1=8191. Not all 2ⁿ-1 numbers are prime (2⁴-1=15=3×5). The Great Internet Mersenne Prime Search (GIMPS) coordinates distributed computing to find new Mersenne primes — the largest known primes are all Mersenne primes (as of 2024, M136279841 with 41 million digits).
Percentage Calculator · Age Calculator · Date Difference · Scientific Calculator · BMI Calculator · Fibonacci Generator