How do you efficiently find prime numbers within a given range?

Finding Prime Numbers in a Given Range

In mathematics, prime numbers are whole numbers greater than 1 that are not divisible by any other number except 1 and themselves. Finding prime numbers within a specific range can be a common programming task. Here's a detailed explanation of how to approach this problem in JavaScript:

Brute Force Approach

The provided code snippet tries to find prime numbers between 0 and 100 using a brute force approach. It checks if the number is divisible by any number from 2 to 12 and returns the number if no divisors are found. However, this approach has several drawbacks:

• It's inefficient, especially for larger ranges.
• It's hard to extend to find primes for bigger ranges.

Sieve of Eratosthenes

A more efficient algorithm for finding prime numbers is called the Sieve of Eratosthenes. Here's how it works:

1. Create an array called sieve with a length of max 1.
2. Initialize all elements in the array to false (assuming false means the number is prime).
3. Iterate through the sieve array from 2 to the square root of max.
4. For each prime number i, mark all its multiples as non-prime by setting sieve[i j] to true for all j from i j to max.
5. After the iteration, the unmarked numbers in the sieve array are prime numbers.

In JavaScript, the code for the Sieve of Eratosthenes looks like this:

<code class="js">function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}</code>

This approach has a time complexity of O(n log log n), which is much more efficient than the brute force approach.

The above is the detailed content of How do you efficiently find prime numbers within a given range?. For more information, please follow other related articles on the PHP Chinese website!