Test whether a number is prime
The number 84 splits into . Both parts split again, and , 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 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 is composite. This is trial division. If the candidates run all the way to , 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 divisions, about ten seconds for one number at 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: , , , and .
In every pair, one of the two divisors is at most 6, the square root of 36. The same holds for any : two divisors that were both larger than would multiply to more than . So if has a divisor other than 1 and itself, it has one that is at most , and the test can stop there.
The loop below runs while , which is the condition without computing a square root. The comparison has to be and not , because has no divisor between 1 and 7, and a loop that stopped before 7 would call 49 prime.
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 is more than 97. For 999,999,937 the candidates are now 2 through 31,622, since and the square of 31,623 is already larger than the number. That is 31,621 divisions in place of almost .
List every divisor in pairs
The same pairs give every divisor of , not only the answer to whether one exists. For each up to that divides , both and its partner are divisors, and every divisor turns up this way, since each one belongs to a pair. When is the square root itself, as 6 is for 36, the partner is again and is recorded once.
def divisors(n):
small, large = [], []
d = 1
while d * d <= n:
if n % d == 0:
small.append(d)
if d != n // d:
large.append(n // d)
d += 1
return small + large[::-1]
print(divisors(36))large[::-1] is the list of partners reversed.
For 36, small collects 1, 2, 3, 4 and 6 in increasing order, and large collects their partners 36, 18, 12 and 9 in decreasing order. Appending the partners in reverse gives the whole list sorted.
Factor a number into primes
Splitting 84 until only primes were left gave . That product is the prime factorization of 84, written with an exponent for a repeated prime: . Every integer greater than 1 has exactly one prime factorization, apart from the order in which the primes are written. That fact is called the fundamental theorem of arithmetic, and this lesson uses it without proving it.
Trial division finds the factorization. We divide by 2 for as long as 2 divides the number, then by 3 in the same way, then by 4, and so on. Here is the loop on 360:
| Try d | Divides? | Divided out | n left |
|---|---|---|---|
| 2 | yes, 3 times | 45 | |
| 3 | yes, 2 times | 5 | |
| 4 | stop: | 5 | |
| after the loop | , so 5 is prime | 5 | 1 |
The loop stops at while 5 is still left, because is more than 5. By then it has tried 2 and 3 and divided each of them out completely, so neither divides the 5 that is left. The prime test from the first part needs only the candidates up to the square root of 5, about 2.24, so 5 is a prime. The same reasoning applies whenever the loop stops: the number left over is 1 or a prime, and when it is a prime, the code adds it after the loop as the last factor.
The candidates include composite numbers such as 4 and 6, and the loop does not need to skip them: a composite candidate cannot divide when its turn comes. A number divisible by 4 is divisible by 2, and a number divisible by 6 is divisible by 2 and by 3, but every 2 and every 3 was divided out earlier. So whenever does divide the number that is left, is a prime.
def factor(n):
out = {}
d = 2
while d * d <= n:
while n % d == 0:
out[d] = out.get(d, 0) + 1
n //= d
d += 1
if n > 1:
out[n] = out.get(n, 0) + 1
return out
for n in [360, 14]:
print(' '.join(f'{p}^{e}' for p, e in factor(n).items()))The dictionary maps each prime to its exponent; factor(360) is {2: 3, 3: 2, 5: 1}.
For 14 the loop divides out one 2 and leaves 7. The next candidate is 3, and is more than 7, so the loop ends and the final if adds the 7. The outer loop runs at most times for the original , and fewer when has small factors, because shrinks each time a factor is divided out.
Deeper read: divisor count, gcd and lcm from the exponents
The factorization gives the number of divisors without listing them. A divisor of is built from zero to three 2s, zero to two 3s and zero or one 5. Each combination gives a different divisor, and every divisor is one of the combinations, so the count is each exponent plus one, multiplied together:
The exponents also show the gcd and the lcm of two numbers. A common divisor can use a prime only as often as both numbers contain it, and a common multiple has to contain each prime as often as either number does. So the gcd takes the smaller exponent of each prime and the lcm takes the larger:
Find every prime below a limit
Trial division answers a question about one number. Some problems ask about every number up to a limit at once:
You get an integer n. Return how many prime numbers are strictly less than n.
Constraints
-
n
Sample 1 · Input
n = 10
Output
4
Sample 2 · Input
n = 0
Output
0
Sample 3 · Input
n = 1
Output
0
Below 10 the primes are 2, 3, 5 and 7, so the first answer is 4. Running the prime test on every number below takes 654,184,149 divisions in all, about 6.5 seconds at operations a second. Most of them are spent on the primes, each of which is tested all the way to its square root.
The sieve of Eratosthenes turns the work around. Instead of searching each number for a divisor, it starts from each prime and marks the multiples of that prime, which are composite because the prime divides them. We keep a true-or-false flag for every number below , all true at first except those of 0 and 1, and go through the numbers from 2 upward. A number whose flag is still true when we reach it is a prime, because any smaller prime that divided it would have marked it already. For each such prime, we set the flags of its multiples to false. Here is the result below 30:
In the figure, crossing out for a prime starts at . The smaller multiples , and so on up to each have a prime divisor below and were crossed out on that prime's turn: 6 is gone on the turn of 2, before 3 has its turn, so 3 starts at 9.
Starting there also lets the outer loop stop early. Once is or more, the first multiple that would cross out is already outside the range, and the same is true of every larger . Below 30 only 2, 3 and 5 do any crossing, because .
def primes_below(n):
if n < 2:
return []
is_p = [True] * n
is_p[0] = is_p[1] = False
p = 2
while p * p < n:
if is_p[p]:
for m in range(p * p, n, p):
is_p[m] = False
p += 1
return [i for i in range(n) if is_p[i]]
print(len(primes_below(10)))
print(primes_below(30))The answer to Count Primes is the length of the list.
Below 30 the sieve sets a flag to false 21 times to remove 18 composites. A few numbers are crossed out more than once, as 12 is by 2 and again by 3. For it crosses out 11,192,868 times and leaves 348,513 primes. Counting the crossings and the final pass over the flags that collects the primes, that is about 16 million steps against 654 million divisions, roughly a fortieth of the work.
Step through the sieve
Step through the sieve. Each step takes the smallest number that is still uncrossed, which is a prime, and crosses out its multiples from its square upward. With Below 30 the crossings add up to the 21 counted above. With Below 100, 7 crosses out numbers as well, the outer loop stops at , and 25 primes are left.
Cost of trial division and the sieve
- Test, list the divisors of, or factor one number $n$
- Candidates up to the square root: 31,621 for the prime 999,999,937, and no memory beyond the answer.
- Prime test on every number below $n$
- Each prime is tested to its square root: 654,184,149 divisions for .
- Sieve below $n$
time, memory - 11,192,868 crossings for , a little over two per number, and one flag per number.
The in the last row grows so slowly that the sieve is close to linear in practice. The cp-algorithms page under Further reading derives it.
Deeper read: factor many numbers with one sieve
A sieve can record more than true or false. If each crossing stores the prime that did it, every composite ends up with one of its prime divisors on file. Factoring then needs no trial division: we look up a prime divisor of , divide it out, and repeat on what is left. A number with nothing on file is itself a prime. Each division at least halves the number, so is fully factored in at most steps, about 20 for numbers up to . The USACO Guide module under Further reading uses this to count the divisors of numbers quickly.
Count a prime factor without computing the number
Sometimes the exponent of a prime can be found for a number that is far too large to write down. The factorial is the product , with , and it grows very quickly: is 3,628,800, and has 35,660 digits.
You get an integer n. Return the number of zeros at the end of , the product .
Constraints
-
n
Sample 1 · Input
n = 3
Output
0
Sample 2 · Input
n = 5
Output
1
Sample 3 · Input
n = 0
Output
0
ends in no zeros and ends in one. Each zero at the end of a number is a factor of 10, and , so the number of zeros is the number of pairs of a 2 and a 5 in the prime factorization of . There are plenty of 2s, since every second number from 1 to is even, while only every fifth supplies a 5. The 5s run out first, so the answer is the exponent of 5 in .
We can count the 5s in without multiplying anything. The multiples of 5 up to 100 are 5, 10, 15 and so on to 100. There are of them, and each holds one 5. Four of them, 25, 50, 75 and 100, are multiples of and hold a second 5, which adds . No number up to 100 is a multiple of 125, so has factors of 5 and ends in 24 zeros. For any :
The brackets mean rounding down, which is what integer division does. The loop keeps a power of 5 in f and adds the quotient of n by f, the number of multiples of f from 1 to :
def trailing_zeroes(n):
zeros, f = 0, 5
while f <= n:
zeros += n // f
f *= 5
return zeros
for n in [3, 5, 100, 10000]:
print(trailing_zeroes(n))For the powers of 5 that fit are 5, 25, 125, 625 and 3,125, so the loop makes five divisions and finds 2,499 zeros in a number it never computes. The same sum with another prime in place of 5 gives the exponent of in .
Common prime and factoring mistakes
Leaving out the check for numbers below 2.
- Where it breaks
- For 1 the loop never runs, since , and the function falls through to its last line, which reports 1 as a prime. The same happens for 0.
- The fix
- Return false for every below 2 before the loop.
Trusting a floating-point square root as the exact integer root.
- Where it breaks
- The number 9,999,999,999,999,999, which needs a
long longin C++, rounds to when it becomes a floating-point value, somath.sqrtin Python andsqrtin C++ both return exactly 100,000,000. The true integer root is 99,999,999, since is larger than the number. As a trial-division bound this only adds one candidate, but code that needs the exact root, such as a count of the perfect squares up to , is off by one. - The fix
- Compare
i * i <= n, writteni <= n / iin C++, or usemath.isqrt(n)in Python.
Dropping the prime that is left after the loop.
- Where it breaks
- Without the final
if n > 1,factor(14)returns only . The loop stops at because , and the 7 is lost. - The fix
- After the loop, a number left above 1 is one more prime factor.
Recall Factor 990 with the trial-division loop. At which candidate does the loop stop, and what does the final `if` add?
Dividing by 2 once leaves 495. Dividing by 3 twice leaves 55. The candidate 4 does not divide 55. Dividing by 5 once leaves 11. The next candidate is 6, and is more than 11, so the loop stops there with 11 left. The final if adds 11, and .
Recall How many zeros does 1000! end in?
Add the quotients of 1000 by the powers of 5 up to 1000: , , and , rounded down. The total is zeros.