**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.

## Tuesday, November 17, 2009

Posted by venu k

9 comments | 8:46 AM

Subscribe to:
Post Comments (Atom)

Hi bro,

ReplyDeleteThe 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

Thank you bond. I forgot to use modulus operator. I will add your script to above list.

ReplyDeleteBut 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.

Yeah Venu, they are system dependent.

ReplyDeleteI 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!

yeah i liked this very much hats off sirji

ReplyDeletealso visit himanshurockat.com my blog

plzz give script of how to find prime factor.?

ReplyDeletethanx a lot

ReplyDeleteits very helpful

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.

ReplyDeleteThanks

Javin

Top 30 Unix command Interview Questions asked in Investment Banks

Hi,

ReplyDeleteSignificantly 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

you can also use GNU 'factor'

ReplyDelete$ time factor 319993

319993: 319993

real 0m0.001s

user 0m0.000s

sys 0m0.000s