Count Primes (Leetcode 204) (Sieve of Eratosthenes) (DCP

Problem Link: https://leetcode.com/problems/count-primes/description/

class Solution:
    def countPrimes(self, n: int) -> int:

        if(n==0 or n==1):
            return 0
        arr=[]
        for i in range(n+1):
            arr.append(0)
        arr[0]=1
        arr[1]=1
        arr[n]=1

        for i in range(2,n+1):
            if(arr[i]==0):
                # Start the loop from i square
                for j in range(i*i, n+1, i):
                    if(j<n+1):
                        arr[j]=1
        
        ans=0
        for i in range(2,n+1):
            if(arr[i]==0):
                ans=ans+1
        # print(arr)
        return ans

Closest Prime Number in Range (Leetcode 2523)

A slight modification to Sieve of Eratosthenes

```python3
class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:

        arr=[]
        for i in range(right+1):
            arr.append(0)
        arr[0]=1
        arr[1]=1
        for i in range(2,right+1):
            if(arr[i]==0):
                for j in range(i*i,right+1,i):
                    if(j<right+1):
                        arr[j]=1
        

        # Traversing from back as the question asks
        # to return the lower numbered pair if multiple
        # such pairs exist
        # From [11, 13] and [17, 19], return [11, 13]

        # Find the second number of the pair
        for i in range(right, left-1, -1):
            if(arr[i]==0):
                second=i
                break
        else:
            return [-1,-1]
        
        # Find the first number of the pair
        for i in range(second-1, left-1, -1):
            if(arr[i]==0):
                first=i
                break
        
        else:
            return [-1,-1]
        minn=second-first
        ans=[first, second]
        for i in range(first-1,left-1,-1):
            if(arr[i]==0):
                second=first
                first=i
                if(second-first <= minn):
                    minn=second-first
                    ans=[first,second]
        
        return ans 
```