Bash Script to Check Prime Number with Output and Explanation

Use a Bash script that takes a number and checks divisibility from 2 up to its square root using a loop; for example, for ((i=2; i*i<=num; i++)); do if ((num % i == 0)); then echo "Not prime"; exit; fi; done; echo "Prime".

Examples

Input2

Output2 is a prime number

Input15

Output15 is not a prime number

Input1

Output1 is not a prime number

How to Think About It

To check if a number is prime, think about whether it can be divided evenly by any number other than 1 and itself. You only need to test divisors up to the square root of the number because larger factors would have smaller matching factors already checked.

Algorithm

1

Get the input number.

2

If the number is less than 2, it is not prime.

3

Check divisibility from 2 up to the square root of the number.

4

If any divisor divides the number evenly, it is not prime.

5

If no divisors are found, the number is prime.

6

Print the result.

Code

bash

#!/bin/bash
read -p "Enter a number: " num
if (( num < 2 )); then
  echo "$num is not a prime number"
  exit
fi
for ((i=2; i*i<=num; i++)); do
  if (( num % i == 0 )); then
    echo "$num is not a prime number"
    exit
  fi
done
echo "$num is a prime number"

Output

Enter a number: 17
17 is a prime number

Dry Run

Let's trace the number 15 through the code

1

Input number

num = 15

2

Check if less than 2

15 >= 2, continue

3

Loop divisors from 2 to sqrt(15) (~3.87)

Check i=2: 15 % 2 != 0; Check i=3: 15 % 3 == 0 (divisible)

4

Result

15 is not a prime number

i	num % i	Divisible?
2	15 % 2 = 1	No
3	15 % 3 = 0	Yes

Why This Works

Step 1: Check numbers less than 2

Numbers less than 2 are not prime by definition, so we handle them first with if (( num < 2 )).

Step 2: Loop up to square root

We only check divisors up to i*i <= num because any factor larger than the square root would have a smaller matching factor.

Step 3: Check divisibility

If num % i == 0, the number is divisible by i and not prime.

Step 4: Print result

If no divisors are found, the script prints that the number is prime.

Alternative Approaches

Using a while loop

bash

#!/bin/bash
read -p "Enter a number: " num
if (( num < 2 )); then
  echo "$num is not a prime number"
  exit
fi
i=2
while (( i*i <= num )); do
  if (( num % i == 0 )); then
    echo "$num is not a prime number"
    exit
  fi
  ((i++))
done
echo "$num is a prime number"

Uses a while loop instead of for; functionally similar but some prefer while for clarity.

Using bc for floating point sqrt

bash

#!/bin/bash
read -p "Enter a number: " num
if (( num < 2 )); then
  echo "$num is not a prime number"
  exit
fi
limit=$(echo "sqrt($num)" | bc)
for ((i=2; i<=limit; i++)); do
  if (( num % i == 0 )); then
    echo "$num is not a prime number"
    exit
  fi
done
echo "$num is a prime number"

Calculates square root with bc for exact limit; requires bc installed.

Check divisibility by 2 separately, then odd numbers

bash

#!/bin/bash
read -p "Enter a number: " num
if (( num < 2 )); then
  echo "$num is not a prime number"
  exit
fi
if (( num == 2 )); then
  echo "$num is a prime number"
  exit
fi
if (( num % 2 == 0 )); then
  echo "$num is not a prime number"
  exit
fi
for ((i=3; i*i<=num; i+=2)); do
  if (( num % i == 0 )); then
    echo "$num is not a prime number"
    exit
  fi
done
echo "$num is a prime number"

Optimizes by skipping even numbers after checking 2; faster for large numbers.

Complexity: O(√n) time, O(1) space

Time Complexity

The script loops from 2 up to the square root of the input number, so the time grows roughly with √n.

Space Complexity

The script uses a fixed amount of memory regardless of input size, so space complexity is constant.

Which Approach is Fastest?

Skipping even numbers after checking 2 reduces iterations roughly by half, making it faster for large inputs.

Approach	Time	Space	Best For
Basic for loop up to sqrt	O(√n)	O(1)	Simple and clear for beginners
While loop up to sqrt	O(√n)	O(1)	Alternative loop style, similar performance
Using bc for sqrt	O(√n)	O(1)	More precise limit calculation, requires bc
Check 2 then odds only	O(√n/2)	O(1)	Faster for large numbers by skipping even checks