Basics 0/129

Numbers and arithmetic · 3 of 4 Advanced

Primes and sieves

Test a number for primality and factor it by trial division up to the square root, and find every prime below a limit with a sieve.

2,564 words · 12 min read

Part 1 of 7 Prime numbers

Test whether a number is prime

The number 84 splits into 6×146 \times 14. Both parts split again, 6=2×36 = 2 \times 3 and 14=2×714 = 2 \times 7, and there the splitting stops, because 2, 3 and 7 are not products of smaller numbers. A prime is an integer greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13 and so on. An integer greater than 1 that has some other divisor, as 84 does, is composite. The numbers 0 and 1 are neither.

To test whether nn is prime, we divide it by 2, then 3, then 4 and so on, and stop at the first remainder of 0, which shows that nn is composite. This is trial division. If the candidates run all the way to n−1n - 1, the slowest inputs are the primes themselves, since nothing divides them and the loop never stops early. For the prime 999,999,937 that is almost 10910^9 divisions, about ten seconds for one number at 10810^8 operations a second.

Most of those candidates are unnecessary, and the divisors of 36 show why. Divisors come in pairs that multiply to the number: 1×361 \times 36, 2×182 \times 18, 3×123 \times 12, 4×94 \times 9 and 6×66 \times 6.

Each divisor dd below 6 has the partner 36/d36 / d above 6, and 6 pairs with itself.

In every pair, one of the two divisors is at most 6, the square root of 36. The same holds for any nn: two divisors that were both larger than n\sqrt{n} would multiply to more than nn. So if nn has a divisor other than 1 and itself, it has one that is at most n\sqrt{n}, and the test can stop there.

The loop below runs while i×i≤ni \times i \le n, which is the condition i≤ni \le \sqrt{n} without computing a square root. The comparison has to be ≤\le and not <<, because 49=7×749 = 7 \times 7 has no divisor between 1 and 7, and a loop that stopped before 7 would call 49 prime.

Sign up to run
def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

print(is_prime(97))
print(is_prime(49))
print(is_prime(1))

For 97 the loop tries 2 through 9 and stops, because 10×10=10010 \times 10 = 100 is more than 97. For 999,999,937 the candidates are now 2 through 31,622, since 31,6222=999,950,88431{,}622^2 = 999{,}950{,}884 and the square of 31,623 is already larger than the number. That is 31,621 divisions in place of almost 10910^9.