Bash Script to Print Prime Numbers in Range

Use a Bash script with a nested loop to check divisibility for each number in the range and print it if no divisor is found, for example: for ((i=start; i<=end; i++)); do prime=1; for ((j=2; j*j<=i; j++)); do if (( i % j == 0 )); then prime=0; break; fi; done; if (( prime == 1 && i > 1 )); then echo $i; fi; done.

Examples

Inputstart=1, end=5

Output2 3 5

Inputstart=10, end=20

Output11 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 can be divided evenly by any number from 2 up to its square root. If no divisor is found, the number is prime and should be printed.

Algorithm

1

Get the start and end values of the range.

2

For each number from start to end:

3

Check if the number is greater than 1.

4

For each potential divisor from 2 to the square root of the number:

5

If the number is divisible by the divisor, mark it as not prime and stop checking.

6

If no divisors are found, print the number as it is prime.

Code

bash

read -p "Enter start of range: " start
read -p "Enter end of range: " end
for ((i=start; i<=end; i++)); do
  if (( i > 1 )); then
    prime=1
    for ((j=2; j*j<=i; j++)); do
      if (( i % j == 0 )); then
        prime=0
        break
      fi
    done
    if (( prime == 1 )); then
      echo $i
    fi
  fi
done

Output

Enter start of range: 10
Enter end of range: 20
11
13
17
19

Dry Run

Let's trace the script for the range 10 to 12.

1

Check number 10

Check divisors 2 and 3; 10 % 2 == 0, so 10 is not prime.

2

Check number 11

Check divisors 2 and 3; no divisor divides 11 evenly, so 11 is prime.

3

Check number 12

Check divisors 2 and 3; 12 % 2 == 0, so 12 is not prime.

Number	Divisor Checked	Is Prime?
10	2	No
11	2,3	Yes
12	2	No

Why This Works

Step 1: Loop through the range

The script checks every number from the start to the end of the range to test if it is prime.

Step 2: Check divisibility

For each number, it tests divisibility by numbers from 2 up to its square root to find any factors.

Step 3: Print prime numbers

If no divisor is found, the number is prime and is printed to the screen.

Alternative Approaches

Using a function to check primality

bash

is_prime() {
  local num=$1
  if (( num <= 1 )); then
    return 1
  fi
  for ((i=2; i*i<=num; i++)); do
    if (( num % i == 0 )); then
      return 1
    fi
  done
  return 0
}

read -p "Start: " start
read -p "End: " end
for ((n=start; n<=end; n++)); do
  if is_prime $n; then
    echo $n
  fi
done

This approach improves readability by separating the prime check into a function but has similar performance.

Using the Sieve of Eratosthenes (for large ranges)

bash

#!/bin/bash
read -p "Start: " start
read -p "End: " end
size=$((end+1))
declare -a sieve
for ((i=2; i<size; i++)); do
  sieve[i]=1
 done
for ((i=2; i*i<=end; i++)); do
  if (( sieve[i] == 1 )); then
    for ((j=i*i; j<=end; j+=i)); do
      sieve[j]=0
    done
  fi
done
for ((i=start; i<=end; i++)); do
  if (( i > 1 && sieve[i] == 1 )); then
    echo $i
  fi
done

This method is faster for large ranges but uses more memory and is more complex to implement.

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

Time Complexity

The script checks each number in the range (n numbers) and for each number checks divisors up to its square root, resulting in O(n * sqrt(n)) time.

Space Complexity

The script uses a few variables and no extra arrays, so space complexity is O(1).

Which Approach is Fastest?

The Sieve of Eratosthenes is faster for large ranges (O(n log log n)) but uses more memory, while the simple divisor check is easier and uses less memory.

Approach	Time	Space	Best For
Simple divisor check	O(n * sqrt(n))	O(1)	Small to medium ranges
Function-based check	O(n * sqrt(n))	O(1)	Improved readability, similar speed
Sieve of Eratosthenes	O(n log log n)	O(n)	Large ranges, better performance