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.