Topic:
Count the number of primes less than the non-negative integer n.
Example:
- Example 1:
Enter n = 10
Output: 4
Explanation: There are four prime numbers less than 10:2, 3, 5, and 7.
Copy the code- Example 2:
Enter n = 0
Output: 0
Copy the code- Example 3:
Enter n = 1
Output: 0
Copy the codeTip:
- 0 <= n <= 5 *
The topic
Ideas:
Go from 2 to n, and see if they’re prime
A prime number, also known as a prime number, is a natural number greater than 1 that is not divisible by any other natural number except 1 and the number itself. (It can also be defined as a number that has only 1 and the number itself as two positive factors.)
The question then becomes how to tell if it is a prime number:
- The current num number is divided by the number from 2 to num-1 to determine if there is a number with mod 0. If there is a number, it is not prime
- SQRT (num) : If num is not prime and the first array divisible by num is less than or equal to the square root of num, then math.sqrt (num)
/ * *
* @param {number} n
* @return {number}
* /
var countPrimes = function(n) {
if (n < 2) return 0
let _result = 0
for (let i = 2; i < n; ++i) {
_result += isPrime(i)
}
// Check if it is prime
function isPrime(num) {
let index = 2.
max = Math.sqrt(num)
while (index <= max) {
if (num % index == 0) return false
index++
}
return true
}
return _result
}
Copy the codeErichsen screen
If x is prime, then multiples of x greater than x 2x,3x… It’s definitely not prime
Declare an array of length n (prime by default), fill all non-prime arrays with false and count the number of primes encountered
Counting and filling logic can be contained in a loop if the logical fill of non-prime numbers is the array after the current number
var countPrimes = function(n) {
if (n < 2) return 0
let isPrime = Array(n).fill(true),
_result = 0
for (let i = 2; i < n; ++i) {
if (isPrime[i]) {
_result += 1
let index = i * i
while (index < n) {
isPrime[index] = false
index += i
}
}
}
return _result
}
Copy the codeBlog: Front end little bookboy
Every day a daily problem, write the solution of the problem will be updated to the public account one day a big Lee column welcome to pay attention to the message
Public number: front end little bookboy