IntermediateMath for DSABit Manipulation & Math
Primes: check up to √n, or sieve them all
If n has a divisor, one of them is ≤ √n, so checking stops there. For all primes below n, cross out multiples: the Sieve of Eratosthenes.
The idea
Divisors come in pairs: if a × b = n, one of a and b is at most √n. So to test one number, try divisors 2..√n: O(√n) instead of O(n).
To find every prime below n, start with all numbers marked prime and, for each prime p, cross out p², p² + p, p² + 2p, … (smaller multiples were already crossed out by smaller primes).
Worked example
Primes below 20
- p = 2: cross out 4, 6, 8, …, 18
- p = 3: start at 9 and cross out 9, 12, 15, 18 (12 and 18 were already gone)
- p = 5: 25 ≥ 20, stop. Left: 2, 3, 5, 7, 11, 13, 17, 19.
In code (Python)
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
def count_primes(n): # primes < n
if n < 3:
return 0
prime = [True] * n
prime[0] = prime[1] = False
p = 2
while p * p < n:
if prime[p]:
for multiple in range(p * p, n, p):
prime[multiple] = False
p += 1
return sum(prime)is_prime: O(√n). Sieve: O(n log log n) time, O(n) space.
How to spot it
- “count primes”, “prime factors”, “is n prime”, many prime checks at once (use the sieve).
Common mistakes
- Looping to n instead of √n.
- Treating 1 as prime.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →