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:

1. Write all numbers from 2 to N
2. Start at 2 (first prime). Mark all multiples of 2 as composite (4, 6, 8, 10...)
3. Move to 3 (next unmarked number). Mark all multiples of 3 as composite (6, 9, 12...)
4. Move to 5 (next unmarked). Mark multiples of 5...
5. Continue until you've processed numbers up to √N
6. 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)

This article is for informational purposes only. See our disclaimer.