Count the number of prime numbers less than a non-negative number, n
.
Example 1:
Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 0
Constraints:
0 <= n <= 5 * 106
Source
def count_primes(n):
"""Obvious intuition but too slow beyond n = 10*5, whereas n <= 5*106."""
primes = set()
if n >= 3:
primes.add(2)
for number in range(3, n, 2): # only consider odd numbers
if any(number % prime == 0 for prime in primes):
continue
else:
primes.add(number)
return len(primes)
def count_primes(n):
"""Sieve of Eratosthenes
https://www.geeksforgeeks.org/prime-numbers/
https://labuladong.gitbook.io/algo-en/iv.-high-frequency-interview-problem/print_primenumbers
Time Complexity O(log(logn))
Other algorithm solving this problem:
- Segmented Sieve
- Sieve of Sundaram
- Bitwise Sieve
"""
if n < 2:
return 0
strikes = [1] * n # strike list for the input range, initialized at 1
strikes[0] = 0
strikes[1] = 0
for i in range(2, int(n**0.5)+1):
if strikes[i] != 0:
strikes[i*i:n:i] = [0] * len(strikes[i*i:n:i])
return sum(strikes)
def count_primes(n):
"""Sieve of Eratosthenes with optimizations"""
if n < 3:
return 0
sieve = [1] * (n-2)
for t in range(2, ceil(sqrt(n))):
if sieve[t-2] == 1:
sq = t**2
sieve[sq-2 : n : t] = [0] * ((n-1)//t - t + 1)
return sum(sieve)
count_primes(10)
4
count_primes(0)
0
count_primes(1)
0
count_primes(10**5)
9592
count_primes(5*10**6)
348513