204 count primes

204. Count Primes

题目: https://leetcode.com/problems/count-primes/

难度:

Easy

这个题的hint是已经把算法喂到嘴边了

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
  if A[i] is true:
    for j = i^2, i^2+i, i^2+2*i, i^2+3i, ..., not exceeding n :
      A[j] := false

Output: all i such that A[i] is true.

python算法

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        isPrime = [1 for i in range(n)]

        i = 2
        while i * i < n:
            if isPrime[i]:
                j = i * i 
                while j < n :
                    isPrime[j] = 0
                    j += i
            i += 1

        return sum(isPrime[2:])

---

我们一直在努力

apachecn/AiLearning

---