Prime Number Sieve: Finding All Primes Up to N
A prime number is divisible only by 1 and itself: 2, 3, 5, 7, 11, 13, 17, 19, 23...
Finding primes gets computationally harder as numbers get larger — modern cryptography (RSA encryption, HTTPS) depends on the difficulty of factoring very large numbers into their prime components.
The Sieve of Eratosthenes
Named for the Greek mathematician who described it around 240 BCE. The algorithm:
- Write all numbers from 2 to N
- Start at 2 (first prime). Mark all multiples of 2 as composite (4, 6, 8, 10...)
- Move to 3 (next unmarked number). Mark all multiples of 3 as composite (6, 9, 12...)
- Move to 5 (next unmarked). Mark multiples of 5...
- Continue until you've processed numbers up to √N
- All remaining unmarked numbers are prime
Why √N Is the Stopping Point
If a number n has a composite factor, at least one factor must be ≤ √n. So if you've eliminated all composites for primes up to √N, every remaining number must be prime.
For N = 100: √100 = 10. You only need to sieve primes 2, 3, 5, 7 (primes ≤ 10) to find all primes up to 100.
Primes and Cryptography
RSA encryption works by multiplying two large prime numbers (each hundreds of digits long). The product is public. Finding the two prime factors from the product is computationally infeasible for large enough primes — that's the security.
A 2,048-bit RSA key uses primes of roughly 617 decimal digits. Factoring the public key would require more computing time than the age of the universe with current algorithms.
[Find prime numbers →](https://doesitaddup.com)
Frequently Asked Questions
How high can I sieve? Is there a maximum number?
Most sieve calculators can handle numbers up to several million without performance issues. Very large numbers (billions+) may take longer to process depending on your device, but the Sieve of Eratosthenes remains efficient because it only needs to check factors up to √N. For practical purposes, you can sieve comfortably up to 10 million or higher on modern computers.
Why does the calculator only check up to the square root of my number?
If a number n has a composite factor, at least one of those factors must be ≤ √n. So once you've marked all multiples of primes up to √N as composite, every remaining unmarked number is guaranteed to be prime. For example, when finding all primes up to 100, you only need to sieve multiples of 2, 3, 5, and 7 (the primes ≤ 10) because √100 = 10.
Can I use this tool to find prime factors for encryption/cryptography?
This sieve finds all primes up to N, but it's not designed to factor large composite numbers—which is what cryptography relies on. RSA encryption uses primes with hundreds of digits, and factoring their product is computationally infeasible. Use this tool to understand how primes work, but industrial cryptography depends on much more specialized (and secure) mathematics.
What's the difference between this sieve and just checking if each number is prime individually?
The Sieve of Eratosthenes is dramatically faster because it eliminates multiples in batches rather than testing each number separately. For finding all primes up to 100, the sieve marks off all multiples of 2, then 3, then 5, etc.—eliminating composites efficiently in one pass. Testing each number individually would require many more division operations, making it much slower for large ranges.
This article is for informational purposes only. See our disclaimer.