204. Count Primes-白红宇

204. Count Primes

阅读量：4975 次

发布时间：2019-06-12

本文共 1696 字，大约阅读时间需要 5 分钟。

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

Example:

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

Approach #1: C++.

class Solution {public:    int countPrimes(int n) {        vector
     
       matrix(n+5, 1);        helper(n, matrix);        int ans = 0;        if (n <= 1) return 0;        for (int j = 2; j < n; ++j)             if (matrix[j] == 1)                ans++;        return ans;    }        void helper(int n, vector
      
       & matrix) {        for (int i = 2; i*i < n; ++i) {            if (matrix[i] == 1)                for (int j = i+i; j <= n; j += i) {                    matrix[j] = 0;                }        }    }};

Approach #2: Java.

class Solution {    public int countPrimes(int n) {        boolean[] notPrime = new boolean[n];        int count = 0;        for (int i = 2; i < n; ++i) {            if (notPrime[i] == false) {                count++;                for (int j = 2; i*j < n; ++j) {                    notPrime[i*j] = true;                }            }        }        return count;    }}

Approach #3: Python.

class Solution:    def countPrimes(self, n):        """        :type n: int        :rtype: int        """        if n < 3:            return 0        primes = [True] * n        primes[0] = primes[1] = False        for i in range(2, int(n**0.5)+1):            if primes[i]:                primes[i*i : n : i] = [False] * len(primes[i*i : n : i])        return sum(primes)