Given an integer n, return the number of prime numbers that are strictly less than n.

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

Solution

Code

• python

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 1:
            return 0

        tmp = [True] * n

        for i in range(2, n):
            if(tmp[i]):
                for j in range(i*i, n, i):
                    tmp[j] = False

        ret = 0
        for i in range(2, n):
            if tmp[i]:
                ret += 1

        return ret

• full code

import math
class Solution:
    def countPrimes(self, n):
        if n <= 1:
            return 0

        tmp = [True] * n

        # i的倍数都是合数
        # 逆向思维
        for i in range(2, n):
            # 可以有效避免重复计算
            if(tmp[i]):
                for j in range(i*i, n, i):
                    tmp[j] = False
        #从头开始计算
        ret = 0
        for i in range(2, n):
            if tmp[i]:
                ret += 1

        return ret

    # def isPrime(self,x):
    #     for i in range(2, int(math.sqrt(x))+1):
    #         if (x % i == 0):
    #             return False
    #     return True

S = Solution()
# print("********************************")
# print(S.countPrimes(10))
print(S.countPrimes(1500000))