Shell Script to Find Prime Number

Reposted on 18-06-2011 and Method 4 was deleted.

The simplest primality test is as follows: Given an input number n,
check whether any integer m from 2 to n − 1 divides n. If n is divisi-
ble by any m then n is composite, otherwise it is prime.

Method 1:
Now most people who write finding  prime number in shell script(Almost
in all languages) may start with something simple, like:

#!/bin/bash
# SCRIPT: prime1.sh
# USAGE : ./prime1.sh
# PURPOSE: Finds whether given number is prime or not
#####################################################################

echo -n "Enter a number: "
read num
i=2

while [ $i -lt $num ]
do
  if [ `expr $num % $i` -eq 0 ]
  then
      echo "$num is not a prime number"
      echo "Since it is divisible by $i"
      exit
  fi
  i=`expr $i + 1`
done

echo "$num is a prime number "

Output:
[root@venu ]# ./prime1.sh
Enter a number: 1879
1879 is a prime number
[root@venu ]# ./prime1.sh
Enter a number: 119
119 is not a prime number
Since it is divisible by 7

Using here string you can supply input non interactively.

[root@venu ]# ./prime1.sh  <<<2239
Enter a number: 2239 is a prime number

 However, rather than testing all m up to n−1, it is only necessary to
test m up to sqrt n: if n is composite then it can be factored into
two values,at least one of which must be less than or equal to sqrt n.

 Don't use method 1, it is very worst method, I hope that you will
agree with me at the end of this post.

Method 2a:
#!/bin/bash
# SCRIPT: prime2a.sh
# USAGE : ./prime2a.sh
# PURPOSE: Finds whether given number is prime or not
#####################################################################

echo -n "Enter a number: "
read num

#####################################################################
#                       Integer Validation                          #
#####################################################################

# If you are a  beginner you can skip this integer validation block.

expr $num + 1  &> /dev/null

if [ $? -ne 0 ]
then
    echo "Sorry, You supplied non numerical value"
    exit 1
fi

[ $num -lt 2 ] && echo "Values < 2 are not prime numbers" && exit 1

#####################################################################
#                Main Script Starts Here                            #
#####################################################################

i=2
sqrtofnum=`echo "sqrt($num)"|bc`

while [ $i -le $sqrtofnum ]
do
  if [ `expr $num % $i` -eq 0 ]
  then
      echo "$num is not a prime number"
      echo "Since it is divisible by $i"
      exit
  fi
  let i++
done

echo "$num is a prime number "

Output:
[root@venu ]# ./prime2a.sh <<<169
Enter a number: 169 is not a prime number
Since it is divisible by 13
[root@venu ]# ./prime2a.sh <<<3181
Enter a number: 3181 is a prime number

Here is same method without using bc command:

Method 2b:
#!/bin/bash
# SCRIPT: prime2b.sh
# USAGE : ./prime2b.sh
# PURPOSE: Finds whether given number is prime or not
#####################################################################

echo -n "Enter a number: "
read num

#####################################################################
#                 Integer Validation                                #
#####################################################################

# If you are a beginner you can skip integer validation block.

expr $num + 1  &> /dev/null

if [ $? -ne 0 ]
then
    echo "Sorry, You supplied non numerical value"
    exit 1
fi

[ $num -lt 2 ] && echo "Values < 2 are not prime numbers" && exit 1

#####################################################################
#                Main Script Starts Here                            #
#####################################################################

i=1
newnum=$((num-1))

while [ $((i*i)) -lt $newnum ]
do
  let i++
  if [ `expr $num % $i` -eq 0 ]
  then
      echo "$num is not a prime number"
      echo "Since it is divisible by $i"
      exit
  fi
done

echo "$num is a prime number "

Output:
[root@venu ]# ./prime2b.sh <<<361
Enter a number: 361 is not a prime number
Since it is divisible by 19
[root@venu ]# ./prime2b.sh <<<3571
Enter a number: 3571 is a prime number

Method 3a:
#!/bin/bash
# SCRIPT: prime3a.sh < Number to check >
# USAGE : ./prime3a.sh
# PURPOSE: Finds whether a given number is prime or not.

#####################################################################
#                       ARGUMENTS CHECKING                          #
#####################################################################

# If you are a beginner you can skip Arguments checking part.

if [ $# -ne 1 ]
then
    echo "Usage: scriptname <number to check>"
    exit 1
fi

expr $1 + 1  &> /dev/null

if [ $? -ne 0 ]
then
    echo "Sorry, You supplied non numerical value"
    exit 1
fi

[ $1 -lt 2 ] && echo "Values < 2 are not prime numbers" && exit 1

#####################################################################
#                   MAIN PROGRAM STARTS HERE                        #
#####################################################################

num=$1
sqrtofnum=`echo "sqrt($num)" | bc `
i=2

while [ $i -le $sqrtofnum ]
do
  if [ $(((num/i)*i)) -eq $num ]
  then
      echo "$num is not a prime number"
      echo "Since it is divisible by $i"
      exit 0
  fi

  let i++           # you can also use i=`expr $i + 1`
done

echo "$num is a prime number"

Output:
[root@venu ]# ./prime3a.sh 529
529 is not a prime number
Since it is divisible by 23
[root@venu ]# ./prime3a.sh 3571
3571 is a prime number

Here is same method without using bc command:

Method 3b:
#!/bin/bash
# SCRIPT: prime3b.sh
# USAGE : ./prime3b.sh <Number to check >
# PURPOSE: Finds whether a given number is prime or not.

#####################################################################
#                       ARGUMENTS CHECKING                          #
#####################################################################

# If you are a beginner you can skip Arguments checking part.

if [ $# -ne 1 ]
then
    echo "Usage: scriptname <number to check>"
    exit 1
fi

expr $1 + 1  &> /dev/null
if [ $? -ne 0 ]
then
    echo "Sorry, You supplied non numerical value"
    exit 1
fi

[ $1 -lt 2 ] && echo "Values < 2 are not prime numbers" && exit 1

#####################################################################
#                   MAIN PROGRAM STARTS HERE                        #
#####################################################################

num=$1
newnum=$((num-1))
i=1

while [ $((i*i)) -lt $newnum ]
do

  let i++           # you can also use i=`expr $i + 1`

  if [ $(((num/i)*i)) -eq $num ]
  then
      echo "$num is not a prime number"
      echo "Since it is divisible by $i"
      exit 0
  fi

done

echo "$num is a prime number"

Output:
[root@venu ]# ./prime3b.sh 12009
12009 is not a prime number
Since it is divisible by 3
[root@venu ]# ./prime3b.sh 16127
16127 is a prime number

Now using time command to test which script runs fast.

OUTPUT 1:
[root@venu ]# time sh prime1.sh <<<99991
Enter a number: 99991 is a prime number

real    5m6.590s
user    1m13.882s
sys     3m29.807s
[root@venu ]# time sh prime2a.sh <<<99991
Enter a number: 99991 is a prime number

real    0m0.558s
user    0m0.159s
sys     0m0.409s
[root@venu ]# time sh prime2b.sh <<<99991
Enter a number: 99991 is a prime number

real    0m0.534s
user    0m0.141s
sys     0m0.405s
[root@venu ]# time sh prime3a.sh 99991
99991 is a prime number

real    0m0.037s
user    0m0.034s
sys     0m0.003s
[root@venu ]# time sh prime3b.sh 99991
99991 is a prime number

real    0m0.041s
user    0m0.034s
sys     0m0.007s

OUTPUT 2:
[root@venu ]# time sh prime1.sh <<<319993
Enter a number: 319993 is a prime number

real    16m44.993s
user    4m3.943s
sys     12m17.365s
[root@venu ]# time sh prime2a.sh <<<319993
Enter a number: 319993 is a prime number

real    0m0.883s
user    0m0.218s
sys     0m0.529s
[root@venu ]# time sh prime2b.sh <<<319993
Enter a number: 319993 is a prime number

real    0m0.739s
user    0m0.238s
sys     0m0.494s
[root@venu ]# time sh prime3a.sh 319993
319993 is a prime number

real    0m0.072s
user    0m0.054s
sys     0m0.007s
[root@venu ]# time sh prime3b.sh 319993
319993 is a prime number

real    0m0.089s
user    0m0.061s
sys     0m0.008s

I hope, now you understood, Just one line of code makes the difference.
Method 1 takes more and more time to find prime number.