Description:
Count the number of prime numbers less than a non-negative number, n.
Analyse: start from 2, label 2 * 2, 2 * 3... as false; then move to 3, label 3 * 2, 3 * 3, ...as false; move to 4, since 4 is already labeled as false, go next; move to 5, label 5 * 2, 5 * 3... as false. After enumarate all numbers, scan to count how many primes in the array.
Runtime: 489ms
1 class Solution { 2 public: 3 int countPrimes(int n) { 4 vector<bool> primes(n, true); 5 6 // label all non-prime numbers 7 for (int i = 2; i < n; i++) { 8 if (!primes[i]) continue; 9 int count = 2; 10 while (count * i <= n) { 11 primes[(count++) * i] = false; 12 } 13 } 14 15 // count how many primes in the array 16 int result = 0; 17 for (int i = 2; i < n; i++) { 18 if (primes[i]) result++; 19 } 20 return result; 21 } 22 };
原文：http://www.cnblogs.com/amazingzoe/p/5887347.html