LeetCode＃204. Count prime

Count all less than nonnegative integers  n  The number of prime numbers .

 

Example 1：

Input ：n = 10
Output ：4
explain ： Less than 10 There are a total of 4 individual , They are 2, 3, 5, 7 .
Example 2：

Input ：n = 0
Output ：0
Example 3：

Input ：n = 1
Output ：0

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/count-primes
 

We use Eratosthene screening _ Baidu Encyclopedia

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <3:
            return 0
        else:
            dp=[1]*n # Create array （ First, it defaults to all primes ）
            dp[0],dp[1]=0,0 #0 and 1 Not prime 
            for i in range(2,n):
                for i in range(i*i,n,i): # To optimize , from i*i Just start , Reduce duplication 
                    dp[i]=0
            return sum(dp) # Prime numbers all correspond to 1