numbers Prime Number List & Checker star

How It Works

The tool switches between two different algorithms, each suited to a different question. List mode finds every prime up to a limit using the Sieve of Eratosthenes, one of the oldest algorithms still in everyday use (attributed to the Greek mathematician Eratosthenes, 3rd century BC). Starting from 2, it marks off every multiple of 2 as composite, then moves to the next unmarked number (3) and marks off all its multiples, then the next unmarked number (5), and so on. Whatever survives unmarked once you reach the square root of the limit is prime. For a small example: to sieve up to 30, cross out multiples of 2 (4,6,8,…), then multiples of 3 (6,9,12,…, some already crossed), then multiples of 5 (10,15,…) — since 5×5=25 ≤ 30 but 7×7=49 > 30, you can stop there; whatever remains — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — is the complete list. This runs in O(n log log n) time, meaning it stays fast even as the range grows into the hundreds of thousands.

Check mode answers a different question — is this one specific number prime? — using trial division up to the square root. To test whether n is prime, it is enough to check for divisors from 2 up to √n. The reasoning: if n = a × b with both a and b greater than √n, then a × b would be greater than n, which is impossible. So at least one of the two factors must be √n or smaller, and it will be found before the loop finishes. Example: to check 97, you only need to test divisibility by 2, 3, 5, 7 (since 9² = 81 ≤ 97 but 10² = 100 > 97) — none divide evenly, so 97 is prime.

What to Know

The two modes exist because they trade off differently: the sieve is efficient for producing many primes at once but wastes memory and time if you only care about one number near a huge limit; trial division is efficient for a single check but far too slow if repeated for every number in a large range one at a time. Choosing the right one for the job is exactly why this tool offers both.

• 1 is excluded from the primes by definition and convention — it has only one divisor, not two, which would break the uniqueness of prime factorization if it were allowed in.
• 2 is the only even prime; every other even number is divisible by 2 and therefore composite.
• As numbers grow, primes become rarer on average, but never stop appearing — Euclid proved over two thousand years ago that there are infinitely many.