JavaScript Program to Find Prime Numbers in Range

Use a function that loops through the given range and checks each number with isPrime by testing divisibility up to its square root; for example, function findPrimes(start, end) { const primes = []; for(let i = start; i <= end; i++) { if(isPrime(i)) primes.push(i); } return primes; }.

Examples

Inputstart = 1, end = 10

Output[2, 3, 5, 7]

Inputstart = 10, end = 20

Output[11, 13, 17, 19]

Inputstart = 22, end = 22

Output[]

How to Think About It

To find prime numbers in a range, check each number one by one. For each number, test if it is divisible by any number from 2 up to its square root. If it is not divisible by any, it is prime. Collect all such numbers in the range.

Algorithm

1

Get the start and end values of the range.

2

For each number from start to end, do:

3

Check if the number is prime by testing divisibility from 2 to its square root.

4

If the number is prime, add it to the list of primes.

5

After checking all numbers, return the list of prime numbers.

Code

javascript

function isPrime(num) {
  if (num < 2) return false;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

function findPrimes(start, end) {
  const primes = [];
  for (let i = start; i <= end; i++) {
    if (isPrime(i)) primes.push(i);
  }
  console.log(primes);
  return primes;
}

findPrimes(1, 10);

Output

[2, 3, 5, 7]

Dry Run

Let's trace findPrimes(1, 10) through the code

1

Start loop from 1 to 10

i = 1

2

Check if 1 is prime

1 < 2, so not prime

3

Check if 2 is prime

2 >= 2, check divisors up to sqrt(2) ≈ 1.4, no divisors found, prime

4

Add 2 to primes list

primes = [2]

5

Check 3, 4, ..., 10 similarly

3 prime, 4 not prime, 5 prime, 6 not prime, 7 prime, 8 not prime, 9 not prime, 10 not prime

6

Final primes list

primes = [2, 3, 5, 7]

Number	Is Prime?
1	No
2	Yes
3	Yes
4	No
5	Yes
6	No
7	Yes
8	No
9	No
10	No

Why This Works

Step 1: Check numbers from start to end

We look at each number in the range to decide if it is prime.

Step 2: Test divisibility up to square root

Checking divisibility only up to Math.sqrt(num) is enough because if a number has a factor larger than its square root, the matching factor is smaller.

Step 3: Collect primes in a list

All numbers passing the prime test are saved in an array to return at the end.

Alternative Approaches

Sieve of Eratosthenes

javascript

function sievePrimes(start, end) {
  const sieve = new Array(end + 1).fill(true);
  sieve[0] = false;
  sieve[1] = false;
  for (let i = 2; i * i <= end; i++) {
    if (sieve[i]) {
      for (let j = i * i; j <= end; j += i) {
        sieve[j] = false;
      }
    }
  }
  const primes = [];
  for (let i = start; i <= end; i++) {
    if (sieve[i]) primes.push(i);
  }
  console.log(primes);
  return primes;
}

sievePrimes(1, 10);

This method is faster for large ranges but uses more memory to store the sieve array.

Check divisibility by known primes only

javascript

function findPrimesOptimized(start, end) {
  const primes = [];
  for (let num = start; num <= end; num++) {
    if (num < 2) continue;
    let isPrime = true;
    for (const p of primes) {
      if (p * p > num) break;
      if (num % p === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) primes.push(num);
  }
  console.log(primes);
  return primes;
}

findPrimesOptimized(1, 10);

This reduces checks by testing divisibility only by previously found primes, improving efficiency for larger ranges.

Complexity: O(n * sqrt(m)) time, O(n) space

Time Complexity

For each number in the range (n), we check divisibility up to its square root (sqrt(m)), where m is the number's value, resulting in O(n * sqrt(m)) time.

Space Complexity

We store prime numbers found in an array, which can be up to O(n) in the worst case.

Which Approach is Fastest?

The Sieve of Eratosthenes is faster for large ranges because it avoids repeated divisibility checks but uses more memory.

Approach	Time	Space	Best For
Simple divisibility check	O(n * sqrt(m))	O(n)	Small to medium ranges
Sieve of Eratosthenes	O(n log log n)	O(n)	Large ranges, faster performance
Divisibility by known primes	Better than simple check	O(n)	Medium ranges, optimized checks