Question: https://leetcode.com/problems/count-primes/
Question Name: Count Primes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ # The first and second elements are never used. Otherwise, # primesRecord[i] is for interger i. primesRecord = [False] * n primesCount = 0 for number in xrange(2, n): if primesRecord[number] == False: # Cannot be divided by any smaller integer. This is # a prime nubmer. primesCount += 1 current = number while current < n: # This is a composite number. primesRecord[current] = True current += number return primesCount |