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:
- Dividing with integers which are not multiples of 2’s and 3’s
- 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
Comments
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.
Links
Also see: Generating Twin Primes, Cousin Primes and Sexy Primes
Faster: https://github.com/chadwickboggs/personal-bin-scripts/blob/master/primes
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
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.
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
$