-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode_204_Easy.js
37 lines (30 loc) · 929 Bytes
/
LeetCode_204_Easy.js
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
34
35
36
37
/**
* @param {number} n
* @return {number}
*/
// Problem: Count the number of prime numbers less than a non-negative number, n.
// Input: A non negative number, range is not provided.
// Output: Number of primes (not the ones.)
var countPrimes = function(n) {
if (n<=2) return 0
// Taking an array of (n) in order to cover 0 inclusive and n exclusive.
const table = Array(n).fill(true)
table[0] = table[1] = false
const root = Math.sqrt(n)
// Removing 0 and 1 from the total count.
let total = n - 2
// Counting the index till root so that
for (let i=2;i<=root;i++) {
if (table[i]) {
for (let j=i*i;j<n;j+=i) {
if (table[j]) {
total--
table[j] = false
}
}
}
}
// console.log(table)
// return table.filter(elem => elem).length
return total
};