## 1. Overview

By definition, **a prime number is a natural number greater than 1 that is divisible only by 1 and itself**. Prime numbers are a fundamental subject in mathematics and play an important role in cryptography.

In this tutorial, we’ll explore different ways to check if a number is prime in Bash.

## 2. Using *factor*

The GNU Coreutils package provides the *factor* command for obtaining the prime factors of a natural number:

```
$ factor 24
24: 2 2 2 3
$ factor 5
5: 5
```

A prime number only has itself as a prime factor. Therefore, the output of the *factor* command for a prime number, *X*, takes on the form *X: X*. This means that we can use a regular expression (regex) to match this pattern and detect a prime number:

```
$ factor 19 | grep -qE '^(.*): \1$' && echo 'prime' || echo 'not prime'
prime
```

In this case, **we pipe the output of factor to the grep command**. Using

*grep*, we match a regex representing the required form for prime numbers. The

*-E*option used with

*grep*enables extended regex, while the

*-q*option is for silencing all output from

*grep*.

In fact, we’re only interested in the exit status of *grep*. Therefore, **we use the && and || logical operators to print prime if grep finds a match or not prime if no match is found**.

## 3. Using Trial Division

Alternatively, we can employ a more primitive approach to check if a number is prime without using the *factor* command. One of the simplest methods is to perform trial division.

### 3.1. Theoretical Procedure

**Trial division consists of checking if a given number, n, is divisible by any of the numbers from 2 to the square root of n**. However, the method can be made more efficient by using the fact that prime numbers greater than

*3*can only take on the form

*6k-1*or

*6k+1*where

*k*is a positive integer.

This way, to test if a number, *n*, is prime for numbers greater than *3*, we perform a series of steps:

- check if
*n*is divisible by*2*or*3* - check if
*n*is divisible by numbers of the form*6k-1*or*6k+1*that are less than or equal to the square root of*n*

If *n* satisfies neither condition, then it’s prime.

### 3.2. Implementation

We can implement the procedure in a script named *primality_test.sh*:

```
$ cat primality_test.sh
#!/usr/bin/env bash
is_prime() {
local n="$1"
if [[ ! "$n" =~ ^([0-9]|[1-9][0-9]+)$ ]]; then
echo 'Input must be a natural number (0,1,2,3,...)'
return 1
fi
if [ "$n" -eq 2 -o "$n" -eq 3 ]; then
echo "$n is prime"
return 0
fi
if [ "$n" -le 1 -o "$((n % 2))" -eq 0 -o "$((n % 3))" -eq 0 ]; then
echo "$n is not prime"
return 1
fi
for ((i=5; i*i<=$n; i+=6)); do
if [ "$((n % i))" -eq 0 -o "$((n % (i+2)))" -eq 0 ]; then
echo "$n is not prime"
return 1
fi
done
echo "$n is prime"
return 0
}
```

The *is_prime()* function carries out the primality test. Notably, it performs input validation: if *n* isn’t a natural number, the function prints a message and returns with an exit status of *1*, indicating failure.

Otherwise, the *for* loop inside the function tests if *n* is divisible by *5* or *7*, then by *11* or *13*, continuing this way for forms of *6k-1* and *6k+1* up to a limit that is less than or equal to the square root of *n*.

Next, let’s grant the script execute permissions via *chmod*:

`$ chmod +x primality_test.sh`

Finally, let’s *source* (*.*) the script to make *is_prime()* available in the local shell session:

`$ . primality_test.sh`

Now, **we can test the function for all numbers from 1 to 100 via a for loop**:

```
$ for num in $(seq 1 100); do is_prime "$num" &> /dev/null && echo "$num"; done | xargs
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
```

We suppress the output of the *is_prime()* function by redirecting stdout and stderr to the null device. Then, we use the *&&* logical operator to print a given number only if the exit status of *is_prime()* is *0*, denoting success. Finally, we pipe the result to *xargs* to print the output on a single line.

This way, we obtain all prime numbers within the specified range.

## 4. Conclusion

In this article, we explored two different ways to check if a number is prime in Bash. The first method relied on prime number factorization via the *factor* command, whereas the second approach used manual trial division in the shell to test for primality.