leetcode204

public class Solution {
    public int CountPrimes(int n) {
        if (n <= 2)
            {
                return 0;
            }

            long[] prime = new long[n + 1];
            bool[] mark = new bool[n + 1];

            int primeSize = 0;

            for (int i = 1; i < n; i++)
            {
                mark[i] = false;
            }

            for (long i = 2; i < n; i++)
            {
                if (mark[i] == true)
                {
                    continue;
                }
                prime[primeSize++] = i;
                for (long j = i * i; j <= n; j += i)
                {
                    mark[j] = true;
                }
            }

            return primeSize;
    }
}

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

这道题目是意思是，计算比n小的非负数中有多少素数。

例如：

n = 7，素数有2，3，5（不包含7）一共3个

n = 8，素数有2，3，5，7一共4个

使用素数筛法可以提高效率。

python的实现如下：

 1 class Solution:
 2     def countPrimes(self, n: int) -> int:
 3         nfilter = [False] * n
 4         count = 0
 5         for i in range(2,n):
 6             if nfilter[i]:
 7                 continue
 8             count += 1
 9             k = i + i
10             while k < n:
11                 nfilter[k] = True
12                 k += i
13         return count