Pages

Tuesday, November 17, 2009

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.

9 comments:

  1. Hi bro,

    The following code is also fast and simple:

    ##################################################
    #!/bin/bash

    echo -e "\nScript to find whether the supplied number is a prime number or not\n"

    if [ $# != 1 ]
    then
    echo "Incorrect number of parameters"
    echo "Usage: $0 [Interger Number]"
    exit
    fi

    number=$1

    for (( i=2; i<$number; i++ ))
    do
    rem=$[ $number % $i ]
    if [ $rem -eq 0 ]
    then
    echo "$number is not a prime number"
    exit
    fi
    done

    echo "$number is a prime number"
    ###############################################

    O/P:
    99991 is a prime number

    real 0m2.472s
    user 0m2.280s
    sys 0m0.103s

    ReplyDelete
  2. Thank you bond. I forgot to use modulus operator. I will add your script to above list.
    But it has taken 2 sec more, when compared with methods 3 and 4. Above times are system
    dependent. Run method 3, 4 and your script on your box, and let me know which one is best.

    ReplyDelete
  3. Yeah Venu, they are system dependent.

    I did time check for 3, 4 and my script. Yours are faster :)

    root@bt:~# time ./script3.sh 99991
    99991 is a prime number

    real 0m1.494s
    user 0m1.363s
    sys 0m0.090s

    root@bt:~# time ./script4.sh 99991
    99991 is a prime number

    real 0m1.598s
    user 0m1.503s
    sys 0m0.083s

    root@bt:~# time ./script-mine.sh 99991
    99991 is a prime number

    real 0m2.377s
    user 0m2.260s
    sys 0m0.107s

    Btw, I love your this blog and do practice your scripts my way to keep brushing the scripting skills.
    Gotta busy for next 1 month. Will revert to your scripts after that.

    Good work mate! Keep it up!

    ReplyDelete
  4. yeah i liked this very much hats off sirji

    also visit himanshurockat.com my blog

    ReplyDelete
  5. plzz give script of how to find prime factor.?

    ReplyDelete
  6. thanx a lot
    its very helpful

    ReplyDelete
  7. This is a nice exercise for anyone who is learning scripting in bash and in my opinion best way to learn scripting is to write script. you are doing amazing job on sharing your knowledge on bash man.

    Thanks
    Javin
    Top 30 Unix command Interview Questions asked in Investment Banks

    ReplyDelete
  8. Hi,

    Significantly faster logic...

    ############################################################
    # !/bin/bash
    # Program to check prime number

    # Requires one operator

    if [ $# -lt 1 ] ; then
    echo "Missing operand. usage : $0 [integer]"
    exit 1
    fi


    if [ $(($1%2)) -eq 0 ] ; then
    echo "$1 is not a prime number.It is divisible by 2"
    exit
    fi

    for((i=3;i < $(($1/i));i+=2)) do
    if [ $(($1%i)) -eq 0 ] ; then
    echo "$1 is not a prime number.It is divisible by $i"
    exit
    fi
    done

    echo " $1 is a prime number "
    exit


    time sh primeheck 99991
    99991 is a prime number

    real 0m0.010s
    user 0m0.006s
    sys 0m0.002s

    Thanks,
    Krish



    ReplyDelete
  9. you can also use GNU 'factor'

    $ time factor 319993
    319993: 319993

    real 0m0.001s
    user 0m0.000s
    sys 0m0.000s

    ReplyDelete