204. Count Primes (Python)

Related Topic

Math.

Description

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

Sample I/O

Example 1

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

Note:

• 1 is typically treated as an ugly number.
• Input is within the 32-bit signed integer range: [−231, 231 − 1].

Methodology

Create a list with same length of input number and init all value to True (Suppose all value are prime) except the first two values to False (not prime). Iterate the number of input. Once the current number is prime then all of it’s product is prime and the product must be smaller or equal than n. We marked such product in list as False.

def countPrimes(self, n: int) -> int:
        if n<2: return 0
        prime=[True]*n
        prime[0]=prime[1]=False
        for i in range(2,n):
            if prime[i]:
                for j in range(i+i, n, i):
                    prime[j]=False
        return prime.count(True)

BigO

Time complexity : O(nlogn) where n is input number.