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

**Example:**

1 2 3 |
<strong>Input:</strong> 10 <strong>Output:</strong> 4 <strong>Explanation:</strong> There are 4 prime numbers less than 10, they are 2, 3, 5, 7. |

Key idea is to constructure an array, which at array[i], indicate number i is prime or not.

1. We init the array, and assume all the numbers are prime at first.

2. We start from i = 2, loop through 2 to n

3. Inside every loop, we set the mutiple of i (represent as J) to false. we can set J at j = i * i;

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to *n*. But don’t let that name scare you, I promise that the concept is surprisingly simple.

Sieve of Eratosthenes: algorithm steps for primes below 121. “Sieve of Eratosthenes Animation” by SKopp is licensed under CC BY 2.0.

We start off with a table of *n* numbers. Let’s look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, … must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?

In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, … Now what should be the terminating loop condition?

It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3? Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime. Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
/** * @param {number} n * @return {number} */ var countPrimes = function(n) { let isPrimeArray = []; let count = 0; for (let i = 0; i < n; i++) { isPrimeArray[i] = true; } for (let i = 2; i < n; i++) { if (isPrimeArray[i] === true) { count++; } for (let j = i * i; j < n; j = j + i) { isPrimeArray[j] = false; } } return count; }; |

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/** * @param {number} n * @return {number} */ var countPrimes = function(n) { let isPrimeArray = []; let count = 0; for (let i = 0; i < n; i++) { isPrimeArray[i] = true; } for (let i = 2; i * i < n; i++) { if (!isPrimeArray[i]) { continue; } for (let j = i * i; j < n; j = j + i) { isPrimeArray[j] = false; } } for (let k = 2; k < n; k++) { if (isPrimeArray[k]) { count++; } } return count; }; |

## Recent Comments