leetcode 204

204 Count Primes 质数的个数

Count the number of prime numbers less than a non-negative number, n\. 求小于n的质数的个数

Example:

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

解题思路：质数：一个大于1的自然数中，除了1和此数本身外，没有被其他自然数整除的数

1. The number 1 is neither prime nor composite.

2. if n is a postive integer that does not have a prime divisor less than sqrt(n), the n is prime.

   举例：101 是质数吗？

   the prime less than sqrt(101) : 2,3,5,7

   但是101 都不能被2，3，5，7 整除， 所以101 是prime

​ 举例： 1147 是质数吗？

​ the prime less than sqrt(1147) : 2,3,5,7,11,13,17,23,29,31

​ 1147=31*37,所以1147 是质数

3. if n is a composite postive integer, then n has a prime divior less than sqrt(n)

   埃拉托斯特尼筛法 Sieve of Eratosthenes ：

class Solution:
    def countPrimes(self, n: int) -> int:
        if n<2:
            return 0
        res=[True]*n
        res[0],res[1]=False,False
        
        for i in range(2,n):
            if res[i]==True:
                
                for j in range(i*i,n,i):
                    res[j]=False
        return sum(res)