# Python code for Prime numbers less than n.

### Divit Joshi γ»2 min read

##
**FACTS ABOUT PRIME NUMBERS**

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 = [1]*(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[0] = lst[1] = 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] = [0] * (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 = [1] * n
lst[0] = lst[1] = 0
m = 2
while m * m < n:
if lst[m] == 1:
lst[m * m: n: m] = [0] *(1 + (n - m * m - 1) // m)
m += 1 if m == 2 else 2
return sum(lst)
```