Prime Numbers

Sieve of Eratosthenes

1
2
3
4
5
6
7
8
9

# Time complexity O(MX * log log MX)
MX = 1_000_001
is_prime = [False] * 2 + [True] * (MX - 2)  # 0 and 1 are not prime
primes = []
for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False  # j is a multiple of prime i

204. Count Primes

p[i] represents the number of primes less than or equal to i. Starting from i=2, p[i]==0 <=> i is prime. Then, starting from ii, mark multiples of i as composite (by setting p[ik]=-1). And, p[i] is assigned p[i-1]+1.

If p[i]<0, then i is composite, p[i]=p[i-1].

2523. Closest Prime Numbers in Range