204._count_primes.md

###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:])