Appearance
4.0.5 — Prime Numbers: Check One, List Many, Factorise
Classic · Easy to Medium · LeetCode 204 (Count Primes) · asked in almost every service-company test
The problem
- Say whether a number n is prime.
- Print every prime up to n.
- Break n into its prime factors. 360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5.
A prime is a whole number greater than 1 whose only divisors are 1 and itself. 2, 3, 5, 7, 11 and 13 are prime. 1 is not prime. 4 is not prime because 4 = 2 \times 2. A number greater than 1 that is not prime is called composite.
Why is 1 not prime? Every whole number above 1 can be written as a product of primes in exactly one way, if you ignore the order. This is the fundamental theorem of arithmetic. 12 = 2 \times 2 \times 3, and there is no other set of primes that multiplies to 12. If 1 counted as prime, you could write 12 = 1 \times 2 \times 2 \times 3 or 1 \times 1 \times 2 \times 2 \times 3, and "exactly one way" would fail. So 1 is left out on purpose to keep that rule clean.
1. Is one number prime?
The slow way tries every divisor from 2 to n - 1. For n around a billion, that is a billion divisions.
The first speed-up: stop at \sqrt{n}. This is the pairing idea from 4.0.4. If n = a \times b, then a and b cannot both be bigger than \sqrt{n}, because then a \times b would be bigger than n. So if n has any divisor other than 1 and itself, it has one no bigger than \sqrt{n}. If no number up to \sqrt{n} divides it, it is prime. For a billion, that is about 31,623 checks instead of a billion.
The second speed-up: skip the even numbers. If 2 does not divide n, then no even number does either. So test 2 once, then try only 3, 5, 7, 9, and so on. That halves the work again.
python
def is_prime(n: int) -> bool:
if n < 2:
return False # (1)
if n < 4:
return True # (2) 2 and 3
if n % 2 == 0:
return False # (3)
d = 3
while d * d <= n: # (4)
if n % d == 0:
return False
d += 2 # (5)
return True
print([x for x in range(30) if is_prime(x)])
# → [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(is_prime(1_000_000_007)) # → True(1) 0, 1 and every negative number are not prime.
(2) 2 and 3 are prime. Handling them here keeps the loop simple.
(3) Every other even number is composite.
(4) Try divisors only while d^2 \le n. Using d * d avoids square roots, which are computed with decimals and can be slightly off for very large numbers.
(5) Jump to the next odd number.
A further trick you can mention: the 6k ± 1 rule. Every whole number can be written as 6k, 6k+1, 6k+2, 6k+3, 6k+4 or 6k+5. Four of those are always divisible by 2 or 3. 6k, 6k+2 and 6k+4 are even. 6k+3 is divisible by 3. So every prime above 3 has the form 6k + 1 or 6k + 5, which is the same as 6k - 1. After testing 2 and 3, you only need to try 5, 7, 11, 13, 17, 19 and so on. That checks two numbers out of every six instead of three.
python
def is_prime_6k(n: int) -> bool:
if n < 2:
return False
if n < 4:
return True
if n % 2 == 0 or n % 3 == 0:
return False
d = 5
while d * d <= n:
if n % d == 0 or n % (d + 2) == 0: # tests 6k-1 and 6k+1
return False
d += 6
return True
print(is_prime_6k(97), is_prime_6k(91)) # → True False91 is a good number to test. It looks prime, but 91 = 7 \times 13. The loop starts at d = 5 and tests 5 and 7. 7 divides 91, so it returns False.
2. Every prime up to n: the sieve
Testing each number on its own repeats work. The number 3 gets tried against 9, 15, 21, 27 and every other candidate, over and over. The sieve of Eratosthenes turns the question around. Instead of asking each number "who divides you?", it takes each prime and crosses out all of its multiples.
Eratosthenes was a Greek scholar who ran the library at Alexandria around 240 BC. He also measured the size of the Earth with a stick and a shadow.
python
def primes_up_to(n: int) -> list[int]:
if n < 2:
return []
is_p = [True] * (n + 1) # (1)
is_p[0] = is_p[1] = False
p = 2
while p * p <= n: # (2)
if is_p[p]:
for m in range(p * p, n + 1, p): # (3)
is_p[m] = False
p += 1
return [i for i in range(n + 1) if is_p[i]]
print(primes_up_to(50))
# → [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47](1) One true-or-false box per number. Start by assuming everything is prime.
(2) We only need primes up to \sqrt{n} to cross out every composite. Each composite has a prime factor no bigger than its square root.
(3) Start crossing out at p \times p, not at 2p. Any smaller multiple, like 3p when p = 5, has a smaller prime factor (here 3). That smaller prime already crossed it out.
The sieve by hand, for n = 30
Write down the numbers 2 to 30. Then go round by round.
| round | prime found | crossed out in this round |
|---|---|---|
| 1 | 2 | 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 |
| 2 | 3 | 9, 15, 21, 27 |
| 3 | 4 is already crossed out, skip it | |
| 4 | 5 | 25 |
| 5 | 6 × 6 = 36 is bigger than 30, so stop |
Look at round 2. The prime 3 starts crossing at 9, not at 6. 6, 12, 18, 24 and 30 were already crossed out by 2. So 3 only needs to cross the odd multiples from 9 on.
Look at round 4. The prime 5 starts at 25. Its smaller multiples, 10, 15 and 20, already have a smaller prime factor, 2 or 3. They were crossed out in rounds 1 and 2.
Everything not crossed out is prime: 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. That is 10 primes.
Why we can stop at the square root
After the prime 5, the next prime is 7. Its first new multiple would be 7 \times 7 = 49, which is past 30. Every smaller multiple of 7, like 14, 21 and 28, has a smaller factor and is already gone. So once p \times p is bigger than n, no new number can ever be crossed out. The loop can stop.
How much work it does
The prime 2 crosses out about n/2 numbers. The prime 3 crosses out about n/3. The prime 5 about n/5. So the total is about
n \times \left(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots\right)
The bracket adds up 1/p for the primes up to \sqrt{n}. It grows very, very slowly. Mathematicians write it as \log \log n, "the log of the log of n". Even for n = one billion, it is only about 3. So the sieve does just a few passes' worth of work over the list. That is close to O(n). It needs O(n) memory, one box per number.
4.28.9 measures it: counting the primes below 5 million takes about 0.03 seconds.
Which one to use. For one number, trial division. For all numbers up to a limit, the sieve. The sieve wins once you need more than a few hundred numbers checked.
A useful upgrade: store the smallest prime factor
The plain sieve stores only "prime or not". A small change makes it far more useful. For every number, store its smallest prime factor. Then you can break any number up to n into primes very quickly, with no trial division.
python
def smallest_factor_sieve(n: int) -> list[int]:
spf = list(range(n + 1)) # (1)
p = 2
while p * p <= n:
if spf[p] == p: # (2)
for m in range(p * p, n + 1, p):
if spf[m] == m: # (3)
spf[m] = p
p += 1
return spf
def factorise_fast(x: int, spf: list[int]) -> list[int]:
out = []
while x > 1:
out.append(spf[x]) # (4)
x //= spf[x]
return out
spf = smallest_factor_sieve(1000)
print(factorise_fast(360, spf)) # → [2, 2, 2, 3, 3, 5]
print(factorise_fast(997, spf)) # → [997](1) Start by saying every number is its own smallest factor.
(2) If spf[p] is still p, nothing smaller divides it, so p is prime.
(3) Only write a factor the first time. The first prime to reach m is its smallest prime factor.
(4) The smallest factor of x is one of its primes. Divide it out and repeat with what is left.
Each step at least halves x, so breaking up a number takes about \log_2 x steps. This is the tool to use when a question asks you to factorise thousands of numbers.
Primes in a far-away range: the segmented sieve
Sometimes the question is "print the primes between L and R", where R is huge, like 10^{12}, but the range is short, like one million numbers. You cannot make a list with 10^{12} boxes. But you do not need to.
Every composite number up to R has a prime factor no bigger than \sqrt{R}. For R = 10^{12}, that is one million. So:
- Use the normal sieve to find all primes up to \sqrt{R}.
- Make boxes only for the numbers from L to R.
- For each small prime, cross out its multiples inside that range.
python
from math import isqrt
def primes_in_range(lo: int, hi: int) -> list[int]:
small = primes_up_to(isqrt(hi)) # (1)
is_p = [True] * (hi - lo + 1) # (2) box i stands for lo + i
for p in small:
start = max(p * p, (lo + p - 1) // p * p) # (3)
for m in range(start, hi + 1, p):
is_p[m - lo] = False
return [lo + i for i, ok in enumerate(is_p) if ok and lo + i >= 2]
print(primes_in_range(100, 130)) # → [101, 103, 107, 109, 113, 127](1) The primes up to \sqrt{hi} are enough to cross out every composite in the range.
(2) One box for each number in the range only.
(3) The first multiple of p that is at least lo. (lo + p - 1) // p is lo divided by p, rounded up. Multiplying back by p gives that first multiple. We also never start below p * p, for the same reason as the normal sieve.
This is called the segmented sieve. The same idea also lets a normal sieve work on a huge n piece by piece, so it never needs all the memory at once.
3. Prime factorisation
Break n into the primes that multiply to give it.
The idea is like dividing a cake. Divide out 2 as many times as you can. Then 3. Then 5, and so on. Each time a divisor fits, write it down and divide it out of n.
python
def prime_factors(n: int) -> list[int]:
factors = []
d = 2
while d * d <= n: # (1)
while n % d == 0: # (2)
factors.append(d)
n //= d
d += 1
if n > 1: # (3)
factors.append(n)
return factors
print(prime_factors(360)) # → [2, 2, 2, 3, 3, 5]
print(prime_factors(97)) # → [97]
print(prime_factors(2 * 2 * 1_000_003)) # → [2, 2, 1000003](1) Same square-root limit. But note that n is shrinking as we divide factors out, so the limit shrinks too.
(2) Divide out the same factor as many times as it fits. That is how 360 gives three 2s.
(3) If anything above 1 is left at the end, it is a prime. Why? Every smaller factor has already been divided out, and no divisor up to its square root was found.
Why does d never land on a composite like 4? When d reaches 4, every 2 has already been divided out of n. So 4 cannot divide n any more. The same is true for 6, 8, 9 and every other composite. The loop tries them, but they never fit. This is why the list contains only primes, even though we never checked which d values are prime.
Trace on 360:
d | divides? | n after | factors so far |
|---|---|---|---|
| 2 | yes, 3 times | 45 | 2, 2, 2 |
| 3 | yes, 2 times | 5 | 2, 2, 2, 3, 3 |
| 4 | stop: 4 \times 4 = 16 > 5 | 5 | |
| end | 5 > 1, so add it | 2, 2, 2, 3, 3, 5 |
Complexity
| Task | Time | Memory |
|---|---|---|
| Is n prime? | O(\sqrt{n}) | O(1) |
| All primes to n | O(n \log \log n) | O(n) |
| Factorise n | O(\sqrt{n}) at worst | O(\log n) for the list |
The factor list has at most \log_2 n entries, because every factor is at least 2, and multiplying more than \log_2 n twos would already go past n.
Where this shows up in real life
The security of most of the internet's encryption, including the padlock in your browser, once rested on how hard factorising is. Multiplying two 300-digit primes takes a computer a moment. Splitting the 600-digit product back into those two primes would take longer than the age of the universe with the methods above. That gap is the idea behind RSA encryption, which Part 8 covers.
What the interviewer will push on
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"Why do you only check divisors up to the square root?" If n = a \times b, then a and b cannot both be bigger than \sqrt{n}. Their product would then be bigger than n. So if n has any divisor, it has one at or below \sqrt{n}. If none is found there, n is prime.
"Is 1 a prime? Is 2?" 1 is not a prime. 2 is a prime, and it is the only even prime. Many buggy answers get one of these two wrong.
"Print every prime up to 10 million." Use the sieve of Eratosthenes, not a prime check for each number. Cross out the multiples of each prime, starting from its square. It does the whole job in about one pass over the numbers.
"Why does your factorisation never print 4 or 6?" By the time the loop reaches 4, every 2 has already been divided out of the number. So 4 can no longer divide it. The same happens with every number that is not prime.
"How would you check a 300-digit number?" Trial division is far too slow for that. Real software uses the Miller–Rabin test, a quick test that says "not prime" for sure or "prime" with tiny doubt. Just knowing its name is enough here.
One thing to volunteer: "1 is left out of the primes on purpose, so that every number breaks into primes in exactly one way."
Next: 4.0.6 HCF and LCM. Euclid's 2,300-year-old shortcut, which needs no prime factors at all.