Prime numbers
Instantly check whether a number is prime (and find its smallest divisor if it isn't), or generate the complete list of prime numbers up to 100,000.
How to check whether a number is prime
A number is prime when it has exactly two divisors: 1 and itself. To test it you don't need to try every number — it's enough to look for divisors up to the square root, because if n = a × b, at least one of the two factors must be ≤ √n. This tool tries 2 and 3, then only candidates of the form 6k ± 1 (the only possible primes beyond 3), so the check is instant even for numbers up to one trillion. When the number is not prime, the smallest divisor found is always itself a prime number.
The Sieve of Eratosthenes, a 2,200-year-old algorithm
The list is generated with the method of the Greek mathematician Eratosthenes: write down every number up to the limit, then "sift out" the multiples of each prime you find, starting from its square. Whatever survives is prime. Primes get rarer as you go up: there are 25 of them below 100, 168 below 1,000 and 9,592 below 100,000 — and yet, as Euclid proved, they never run out.