Sieve of Eratosthenes and Long Arithmetic

Primes and the idea of a sieve

A prime is a number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11 ... Every other number greater than 1 is composite (it has a smaller divisor).

You can test one number n by trying to divide it by 2, 3, 4 ... up to √n. But if you want all primes up to n, there is a faster idea, thought of by the Greek scholar Eratosthenes more than 2000 years ago: do not test numbers, remove the ones that cannot be prime.

The algorithm step by step

1. Write all numbers from 2 to n. Mark all of them "maybe prime".
2. Take the smallest number p that is still marked. It is prime.
3. Cross out its multiples p², p² + p, p² + 2p, ... up to n.
4. Go back to step 2. Stop when p × p is bigger than n.
5. Every number still not crossed out is prime.

Why start at p²? A smaller multiple like 5 × 3 was already crossed out when we handled 3. Every composite number has a prime factor that is at most its square root, so primes up to √n are enough.

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= n:
    if is_prime[p]:
        for m in range(p * p, n + 1, p):
            is_prime[m] = False
    p += 1

Speed: about n log log n steps, which is almost linear. For n = 10 million it finishes in a blink. Cost: memory for n flags.

Why we need long arithmetic

A normal integer variable can hold only a limited number. A 64-bit signed integer stops at about 9.2 × 10¹⁸, which has 19 digits. But 21! has 20 digits, and 100! has 158 digits. To work with such numbers, we use long arithmetic: keep the number as a list of digits (often stored with the smallest digit first) and do the school methods on this list.

The list can be as long as the memory allows. (Many languages, such as Python, have this built in; knowing how it works is the point.)

Adding, subtracting and multiplying long numbers

Addition. Go from the right. In every column compute s = a + b + carry. Write s mod 10 (the last digit of s). The new carry is s ÷ 10 (whole part). At the end, if the carry is not 0, write it as a new first digit. Cost: one step per digit, O(n).

Subtraction (bigger − smaller) works the same way but with a borrow instead of a carry: if a digit is too small, borrow 10 from the next column.

Long × small number. For each digit, compute d × k + carry; write the last digit and carry the rest. This is how you build factorials like 50!, multiplying a long number by 2, then 3, then 4 ...

Long × long is done like school multiplication: every digit of one number meets every digit of the other, about n × m steps.

Try it: add by columns, then sieve by hand

1) Write the numbers 2 to 50 in a 7 × 7 grid on paper. Use a red pencil and do exactly what the 3D does. Count how many numbers are left. (You should get 15.) 2) In the 3D, move the column slider and check each column of 874965 + 365879 with a pencil before looking at the answer.

Key formulas and definitions

• Sieve: cross out p², p² + p, p² + 2p, … up to n; stop when p² > n
• Time of the sieve ≈ n log log n
• Long addition, each column: s = a + b + carry; digit = s mod 10; carry = ⌊s / 10⌋
• Long × short: s = d × k + carry; digit = s mod 10; carry = ⌊s / 10⌋
• Number of digits of N ≈ ⌊log₁₀ N⌋ + 1

Worked examples

Common mistakes

• Starting to cross out at 2p instead of p². It still works but wastes steps.
• Crossing out the prime itself. We cross only its multiples, not p.
• Continuing the sieve past √n. It is not needed, and it wastes time.
• Forgetting the last carry in long addition, so 99 + 1 becomes 00 instead of 100.