### Objective

Generating prime numbers within a range using bash script. The technique used in this implementation to generate the prime numbers is still the good old divide and check method, but with some tweaks attempting to make the execution a bit better.

### Approach

The core method is, we check if an integer p is prime by:

1. Dividing with integers which are not multiples of 2’s and 3’s
2. Dividing with integers upto floor ( sqrt ( p ) )

The integer p itself is needed to be not divisible by 2 or 3 or both.

In this implementation we generate integers starting from 5 which are not multiple of 2’s and 3’s and pass them to a function which check if it is a prime or not. Checking of the prime is also done by generating integers not multiple of 2’s and 3’s and upto square root of that number and divide and check if remainder is 0 and return.

The generation of integers not multiple of 2’s and 3’s are done as follows:

```dx = 4
p = 5
WHILE p is within limit
DO
dx = 6 - dx
p = p + dx
DONE
```

The dx generates the sequence 2 4 2 4 2 4 2 4 …. and starting from 5 if this alternating sequence of 2’s and 4’s , with starting value 2 is is used as increment on p assigned with an initial value not multiple of 2 or 3 then we can generate integers which are not multiple of 3’s, like 5, 7, 11, 13, 17, 19, 23, 25, 29, ….

Now we show the bash script

### Sourcecode

```#!/bin/bash
#script to find primes between range
#http://phoxis.org

#Takes an integer as argument, and checks if it is
#a prime number or not. Returns 0 if it is a prime
#or returns 0 otherwise. The integer passed to this
#function should not be a multiple of 2 or 3 or both
function check_prime ()
{
#initilize vars and counters
n="\$1"
di=4
di=\$((6-di))

i=5

#check only upto floor (sqrt (n))
i_lim=\$(echo "sqrt (\$n)" | bc -l)
#drop fractional part
i_lim=\${i_lim%.*}

#divide with only numbers not multiple
#of 2's and 3's and check if n is a prime
while [ \$i -le \$i_lim ]
do
#check if prime and return 1
if ((n%i == 0))
then
return 1
fi
i=\$((i+di))
di=\$((6-di))
done
#if we are here then n is prime, return 0
return 0
}

#Main execusion sequence

#check for bounds and initilize limit variables
if [ \$# -eq 2 ]
then
low=\$1
high=\$2
elif [ \$# -eq 1 ]
then
low=1
high=\$1
else
echo "Usage: \$0 <low_limit> <high_limit>"
exit 1
fi

if [ \$low -ge \$high ]
then
echo "low_limit (\$low) exceeds high_limit (\$high)"
echo "Usage: \$0 <low_limit> <high_limit>"
exit 1
fi

count=0

dx=4
dx=\$((6-dx))

#manually print 2 and 3 is needed
if [ \$low -le 3 ]
then

if [ \$low -le 2 ]
then
count=\$((count+1))
printf "%5d" "2"
fi

count=\$((count+1))
printf "%5d" "3"

low=5
fi

#if the lower limit given is a multiple of
#2 or 3, then update it to the next integer
#which is not a multiple of 2's and 3's
while (((low%3 == 0) || (low%2 == 0)))
do
low=\$((low+1))
done
p=\$low

#generate integers which are not multiple of
#2's and 3's and pass them to check_prime to
#check for prime, and print
while [ \$p -le \$high ]
do
#call check_prime with p. If 0 returned then
#p is prime or not a prime otherwise
check_prime "\$p"
if [ \$? -eq 0 ]
then
count=\$((count+1))
printf "%5d" "\$p"
fi

p=\$((p+dx))
dx=\$((6-dx))
done

echo -e "\n\nTotal \$count Primes generated\n"
```

### Description

The is_prime function takes one argument n which should be an integer and not divisible by 2 or 3 or both. The function checks if the passed integer n is a prime or not simply by dividing the integers not multiple of 2 or 3 or both and upto floor ( sqrt (n) ), generated with the while loop inside the function with the above described process. bc -l is invoked to get the square root of the passed in integer. The -l switch enables the math library of bc and lets us use the sqrt function. The received square root is a floating point number, which is truncated into an integer with the shell substitution i_lim=\${i_lim%.*} . This will remove the matching pattern .* from the right side of the value of the variable, which results in removal of the fraction part of the number. Each integer generated is divided with n , if the remainder is 0 then it returns 1 immediately, else if no integer divides n then the control reaches out of the while loop and 0 is returned.

In the main execution sequence, if two parameters are passed then the first command line parameter is considered as the lower limit and the second is considered to be the upper limit, and if only 1 parameter is passed then it is considered as the upper limit and the lower limit is taken implicitly as 1. The low and high limits are checked if they are reversed. This process will start generating primes starting from 5. So if the lower limit is less than 5 then the 2 and 3 are printer manually with the messy if-then-else nested code block.

If the user enters a lower bound which is a multiple or 2 or 3 or both, then first the lower bound is advanced to the next integer which is not a multiple of 2 or 3 or both. If this is not done the process would not work, as we never check any integer by dividing them with 2 and 3.

Then the while loop takes control. The is_prime is called with integers which are not multiple of 2 or 3 or both, and are generated in the main execution sequence while loop. These two while loops are similar. The while loop inside the function checks if an integer is a prime, and the while loop in the main execution sequence provides the other while loop to integers to check. The main execution sequence prints the integer depending on if it is prime or not decided by is_prime‘s returned value (\$?) .

### Output

Range 100

```\$ ./prime.sh 100
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

Total 25 Primes generated
```

Range 1000

```\$ ./prime.sh 1000
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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  389  397  401  409  419  421  431  433  439  443  449  457  461  463  467  479  487  491  499  503  509  521  523  541  547  557  563  569  571  577  587  593  599  601  607  613  617  619  631  641  643  647  653  659  661  673  677  683  691  701  709  719  727  733  739  743  751  757  761  769  773  787  797  809  811  821  823  827  829  839  853  857  859  863  877  881  883  887  907  911  919  929  937  941  947  953  967  971  977  983  991  997

Total 168 Primes generated
```

Range 1000 to 2000

```\$ ./prime.sh 1000 2000
1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999

Total 135 Primes generated
```

From this process we gain performance by only dividing upto the square root of the integer (proof not given, but is pretty simple). Also by skipping generation and division of multiple of 2’s we save 50% of the divisions, and by skipping multiple of 3’s we reduce more 17% computation that makes 67% less computation than needed for direct divide and check.

## 3 thoughts on “Bash Script: Generating Primes within Range”

1. chadwickboggs says:
1. phoxis says:

Hey, thanks for sharing your code. I had a look at it, it’s a pretty good one.

I ran some quick benchmarks with the ranges [1-100], [1-1000], [1-10000] . For each range I have ran the code in the blog and the code in your link 10 times and used to time the execution with `time’ tool. I am reporting the mean real times of these experiments. The mean values in seconds are reported in the below table. Also, to take the benchmarks I have commented out the “echo” statements which prints the results in stdout. I have added a counter which counts the total number of primes found and print at the end. I did this to make sure that the timing experiments does not account into printing into stdout. Here is the link to your modified code, please point if I messed it up: http://codepad.org/Ftc86rhd

```+-----------+----------+----------+----------+
| Range     | 1-100    | 1-1000   | 1-10000  |
+===========+==========+==========+==========+
| Post      |  0.1078s | 1.55s    | 14.5767s |
+-----------+----------+----------+----------+
+-----------+----------+----------+----------+
```

The table indicates that the code in the blog post is almost by 33% to 53% faster.

I ran both of them in the same interpreter (bash). Can you mention how did you perform the experiments and concluded to your result? This is because it would be interesting to investigate the case, when we both use the sqrt trick, along with the code in the blog uses skipping of generation of multiples of twos and threes, therefore it should have some performance benefits, *if* it does not incur any overhead which surpasses the performance benefits.

2. alty says:

I found a faster code:

6 /tmp/prime.ksh- 100000000000

\$ cat /tmp/prime.ksh-
#!/bin/bash
#set -x

typeset -i x
typeset -i y

function prime
{
((k=\$1/2))
for ((j=2; j<k; j++)) ; do
if (( \$1 % \$j == 0 )) ; then
prime_flag=FALSE
return
fi
done
}

function process_me
{
prime_flag=TRUE
prime \$1
if [[ \${prime_flag} = "TRUE" ]] ; then
echo \$1" is a prime number."
fi
}

i=1

while [ \$i -le \$1 ] ; do
process_me "\$i" &
((i=i+1))
done
wait

\$