Title link: leetcode-cn.com/problems/co…

Looking at this topic, the average person can easily think of using a loop, through a violent way of traversing to check whether each number is prime, and counting.

However, the algorithm complexity of this method is too high, which is good for small range search. If you find all prime numbers from millions or even tens of millions of numbers, the disadvantage of this method will be extremely obvious. So we can use the Eratosthenian sieve to find prime numbers.

Eratosthenes sieve method

Eratostheni sieve method, referred to as Escherichia sieve, also known as prime sieve. This is a simple and time-honored sieve for finding all prime numbers in a range. The principle used is to label the multiples of each prime as composite numbers, starting with 2.

Multiples of a prime number are arithmetic sequences that differ from the prime number itself. This is the key difference between the screening method and the trial division method, which uses prime numbers to test whether each number to be measured is divisible.

The Sieve of Eratosthenes, one of the most efficient ways to list all the small prime numbers, takes its name from the ancient Greek mathematician Eratosthenes and was described in An Introduction to Arithmetic by another ancient Greek mathematician, Nicomachus.

The core idea of this algorithm is to give the range n of values to be screened and find prime numbers p1, P2… , p 𝑘. First use 2 to sieve, that is, leave the 2, the multiples of 2 out; And then we use the next prime number, which is 3, and we keep the 3, and we get rid of multiples of 3; And then we use the next prime number, 5, and we keep the 5, and we get rid of the multiples of 5; And on and on…

As shown below:

The following is the implementation code of the algorithm:

/** * @param {number} n * @return {number} */
var countPrimes = function(n) {
    let count = 0;
    let signs = new Uint8Array(n);

    for (let i = 2; i < n; i++) {
        if(! signs[i -1]) {
            count++;

            for (let j = i * i; j <= n; j += i) {
                signs[j - 1] = true; }}}return count;
};
Copy the code

Square root Accepted

  • 20/20 cases passed (76 ms)
  • Your runtime beats 99.23% of javascript submissions
  • Each node in the linked list (10000 MB)
  • Time complexity: O(n * loglog n)
  • Space complexity: O(n)

References:

  • Eratosthenes sieve – Wikipedia
  • Use JS to find all prime numbers in a range of integers – zero centigrade

More antithesis

Please follow: github.com/leviding/le…

My level is limited, welcome to exchange and share your ideas, welcome big guy criticism and correction.

Scan the QR code below and follow the wechat public account “Technology Chat” to subscribe for more exciting content.