Count Primes Leet Code problem Python














































Count Primes Leet Code problem Python



Count the number of prime numbers less than a non-negative number, n.

Example :
Input : n = 10
output : 4
Explanation : There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:
Input : n = 1
output : 0

To solve this problem we have two approaches.

METHOD 1 (NAIVE APPROACH):

def countPrimes(n):

        #Initilise Count
        count = 0

        #Base Cases in which the answer will be zero
        if n == 0 or n == 1 or n==2:
            return 0
        
        #For all other values of n
        for i in range(2,n):
            flag = True

            #To check the whether the i is prime or not
            for j in range(2,((i//2)+1)):
                if(i % j == 0):
                    flag = False
                    break

            #If True then Count should be incremented by 1
            if (flag == True) :
                count = count + 1
        return count

METHOD 2 (USING DYNAMIC PROGRAMMING):

def countprimes(n):

    #Base case 
    if n == 0:
        return 0
    
    #Set True for all in range n
    primes = [True for i in range(n+1)]
    
    #initilise count
    count = 0
    p = 2
    
    #Loop through all values
    while p*p <= n:
        if primes[p]:
            for i in range(p * 2, n + 1, p):
                primes[i] = False
                
        p += 1

    primes[0], primes[i] = False, False
    
    # Loop through List primes
    for p in range(n):
    
        #If at any value of list it's True then increment the count by 1
        if primes[p]:
            count += 1
    return count

   This article is written by Rohit Bansal Intern at CPPSECRETS

More Articles of ROHIT BANSAL:

Name Views Likes
Print Objects Of a class in Python 223 1
Reverse Each word in a string or sentence Interview Question 163 1
Python - Currency Converter using Free API 110 1
Automorphic Number TCS DIGITAL Program Asked 2 139 1
Program Asked in TCS DIGITAL 185 1
Roman To Integer LEET CODE 429 1
HUG Framework Python 345 1
Count Primes Leet Code problem Python 306 1
Anagram In Python 277 1
Python nntplib %u2014 NNTP protocol client 289 1

Comments