Skip to content

Commit 6631074

Browse files
committed
Update court-primes.js
1 parent 3e067b2 commit 6631074

1 file changed

Lines changed: 33 additions & 1 deletion

File tree

‎leetcode/court-primes.js‎

Lines changed: 33 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,33 @@
1-
1+
/**
2+
* Qusetion:
3+
* Count the number of prime numbers less than a non-negative number, n.
4+
* Url and solution:
5+
* https://leetcode.com/problems/count-primes/
6+
*
7+
* /
8+
/**
9+
* @param {number} n
10+
* @return {number}
11+
*/
12+
var countPrimes = function(n) {
13+
var pHash = {};
14+
var count = 0;
15+
16+
for (var k = 2; k < n; k++) {
17+
pHash[k] = true;
18+
}
19+
// Loop's ending condition is i * i < n instead of i < sqrt(n)
20+
// to avoid repeatedly calling an expensive function sqrt().
21+
for (var i = 2; i * i < n; i++) {
22+
if (!pHash[i]) continue;
23+
for (var j = i * i; j < n; j += i) {
24+
pHash[j] = false;
25+
}
26+
}
27+
28+
for (var l = 2; l < n; l++) {
29+
if (pHash[l]) count++;
30+
}
31+
32+
return count;
33+
};

0 commit comments

Comments
 (0)