Algorithm: Sieve of Eratosthenes

[sophryu99]

https://leetcode.com/problems/count-primes/discuss/435363/Python3-Simple-Code-How-to-Make-Your-Code-Faster.

Code:
lst[m * m: n: m] = [0] *((n-m*m-1)//m + 1)

Code for count primes

def countPrimes(self, n: int) -> int:
        if n < 3: return 0     ###// No prime number less than 2
        lst = [1] * n          ###// create a list for marking numbers less than n
        lst[0] = lst[1] = 0    ###// 0 and 1 are not prime numbers
        m = 2
        while m * m < n:       ###// we only check a number (m) if its square is less than n
            if lst[m] == 1:    ###// if m is already marked by 0, no need to check its multiples.
			
			    ###// If m is marked by 1, we mark all its multiples from m * m to n by 0. 
			    ###// 1 + (n - m * m - 1) // m is equal to the number of multiples of m from m * m to n
                lst[m * m: n: m] = [0] *(1 + (n - m * m - 1) // m)
				
			###// If it is the first iteration (e.g. m = 2), add 1 to m (e.g. m = m + 1; 
			### // which means m will be 3 in the next iteration), 
            ###// otherwise: (m = m + 2); This way we avoid checking even numbers again.	
            m += 1 if m == 2 else 2
        return sum(lst)

[sophryu99]

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so.

• By definition, for every prime number, it has to check the multiples of the prime and mark it as complete
• The process continues until a value p which is the highest prime number is less than n

1. Given a number N, list out all the numbers from 2 to N

2. Mark all numbers which are divisible by 2 and are greater than equal to the square of it

3. Move to the next unmarked number 3 and repeat the process and continue until the table will look like below

So the prime numbers are the unmarked ones: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

[sophryu99]

Implementation

class Solution:
    def countPrimes(self, n: int) -> int:
        prime = [0 for _ in range(n + 1)]
        p = 2
        while p * p <= n:
            if prime[p] == 0:
                # Update all the multiples of p
                for i in range(p * p, n, p):
                    prime[i] = 1
            p += 1

        if n < 2:
            return 0
        return n - sum(prime) - 2

Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(n)