forked from lightningtgc/JavaScript-Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcourt-primes.js
More file actions
33 lines (30 loc) · 735 Bytes
/
court-primes.js
File metadata and controls
33 lines (30 loc) · 735 Bytes
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
26
27
28
29
30
31
32
33
/**
* Qusetion:
* Count the number of prime numbers less than a non-negative number, n.
* Url and solution:
* https://leetcode.com/problems/count-primes/
*
* /
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
var pHash = {};
var count = 0;
for (var k = 2; k < n; k++) {
pHash[k] = true;
}
// Loop's ending condition is i * i < n instead of i < sqrt(n)
// to avoid repeatedly calling an expensive function sqrt().
for (var i = 2; i * i < n; i++) {
if (!pHash[i]) continue;
for (var j = i * i; j < n; j += i) {
pHash[j] = false;
}
}
for (var l = 2; l < n; l++) {
if (pHash[l]) count++;
}
return count;
};