There are some facts about prime numbers you should know to reduce the time
complexity before we start building its logic😎
o and 1 are not a prime number
2 is the only even prime numbers
multiples of prime number are not prime
what i'll do is take a list of all the the numbers from 0 to n and assign the value 1(True).
lst = *(n)
now for corner cases if n<2 than than there are zero prime numbers less than 2
if(n<2): return 0
now we know that zero and one are not prime
lst = lst = 0
As we know the first prime number is 2 so we take m = 2 and turn all the multiples of m to 0(false) as multiples of prime are not prime.
m = 2 while(m*m < n)://if multiples is out the list than stop! if(lst[m] == 1)://means it is prime lst[m*m : n : m] =  * (1 + (n - m * m - 1)//m) //assigning multiples of prime with zero //(1 + (n - m * m - 1)//m) is equal to the number of multiples from m to n if(m == 2): m += 1 else: m += 2 // This avoid checking even numbers again print(sum(lst)) // adds up all the ones(primes) in the list
Here is the whole code for this
if n < 2: return 0 lst =  * n lst = lst = 0 m = 2 while m * m < n: if lst[m] == 1: lst[m * m: n: m] =  *(1 + (n - m * m - 1) // m) m += 1 if m == 2 else 2 return sum(lst)