LeetCode 204. Count Primes

Description

https://leetcode.com/problems/count-primes/

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.

Explanation

pre calculate all primes numbers less than or equal to the given number

Python Solution

class Solution:
    def countPrimes(self, n: int) -> int:        
        is_primes = self.get_is_primes(n)
        
        count = 0
        for i in range(2, n):
            if is_primes[i]:
                count += 1
        
        return count
            
    def get_is_primes(self, number): 
        is_primes = [True for i in range(0, number + 1)]
                     
        for i in range(2, number):
            if is_primes[i] == False:
                continue
            j = 2
            while i * j <= number:
                is_primes[i * j] = False
                j += 1
        
        return is_primes
  • Time complexity: O(N^2).
  • Space complexity: O(N).

One Thought to “LeetCode 204. Count Primes”

Leave a Reply

Your email address will not be published. Required fields are marked *