Bash Script: Generating Primes within Range

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

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