[leetCode] 204. Count Primes (Python)

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

 

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solution

class Solution:
    def getPrimaryNum_Eratos(N): 
        nums = [True] * (N + 1) 
        
        for i in range(2, len(nums) // 2 + 1): 
            if nums[i] == True: 
                for j in range(i+i, N, i): 
                    nums[j] = False 
        return [i for i in range(2, N) if nums[i] == True]
    
    def countPrimes(self, n: int) -> int:
        prime_nums = Solution.getPrimaryNum_Eratos(n)
        
        return len(prime_nums)

SOMJANG/CODINGTEST_PRACTICE