Pages

Friday, June 24, 2011

Shell Script to Find Prime Factors of a Number


In number theory, the prime factors of a positive integer are the prime numbers
that divide that integer exactly, without leaving a remainder. The process of
finding these numbers is called integer factorization, or prime factorization.
The fundamental theorem of arithmetic says that every positive integer has a
unique prime factorization.

Example:

The prime factors of 330 are 2, 3, 5 and 11:

330 = 2 × 3 × 5 × 11

There is no other possible set of prime numbers that can be multiplied to
make 330.

You can find prime factors of a number using UNIX/Linux utility factor. This is
a very convenient and cool UNIX command. Here is its syntax:

$ factor 330
330: 2 3 5 11
$ factor 2121977
2121977: 11 11 13 19 71

Many Algorithms have been devised for determining the Prime factors of a given
number. They vary quite a bit in sophistication and complexity. It is very diff-
icult to build a general-purpose algorithm for this computationally "hard" prob-
lem, so any additional information which is known about the number in question
or its factors can often be used to save a large amount of time.

Here I am providing a shell script to find prime factors of a positive integer.
This script does most factorizations within a second. In the worst case scenario
(for some large semi-primes with more than 6-digit factors) factorization will
take a couple of minutes to hours.

#!/bin/bash
# SCRIPT: primefactors.sh
# USAGE : primefactors.sh <Positive Integer>
# PURPOSE: Produces prime factors of a given number.
#
###############################################################################
# Arguments Checking #
###############################################################################

if [ $# -ne 1 ]
then
echo "Usage: scriptname <Positive Integer>"
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

num=$1

###############################################################################
# Functions #
###############################################################################
# To know how to find prime number check bellow link:
# Shell script to find prime number
# Bellow function finds supplied argument is a prime or not.

primenumber()
{
primenum=$1
for ((counter2=2;$((counter2*counter2))<=$primenum;counter2++))
do
if [ $((primenum%counter2)) -eq 0 ]
then
return 1
fi
done
return 0
}

primefind()
{
# It's good to check that the number it self is a prime or not before going to
# find prime factors of a number. Comment out bellow line and supply a prime
# number or semi-prime, you will find the difference.
# Ex: primefactors.sh 2121979

primenumber $1 && echo "$1" && exit 0

for ((counter1=$2;counter1<=$1;counter1++))
do
primenumber $counter1 && factorcheck $1 $counter1 && break
done
}

factorcheck()
{
prime=$2
newnum=$1
remainder=$((newnum%prime))

if [ $remainder -eq 0 ]
then
printf "%dx" $prime
newnum=$((newnum/prime))
primefind $newnum 2
return
else
let prime++
primefind $newnum $prime
fi
}

###############################################################################
# Main #
###############################################################################

echo -n "Prime Factors of $1: "
primefind $num 2
printf "\b \n" # \b is used for removing last x.

OUTPUT:
[root@venu ]# sh primefactors.sh
Usage: scriptname
[root@venu ]# sh primefactors.sh 21219797
Prime Factors of 21219797: 101x210097
[root@venu ]# sh primefactors.sh 212197
Prime Factors of 212197: 443x479

Running time of script doesn't depend on number,it depends on number of factors,
more factors less time and less factors more time.

[root@venu ]# time sh primefactors.sh 9999999999999999
Prime Factors of 9999999999999999: 3x3x11x17x73x101x137x5882353

real 0m1.345s
user 0m1.225s
sys 0m0.091s

[root@venu ]# time sh primefactors.sh 999999999995
Prime Factors of 999999999995: 5x251x1831x435179

real 1m32.105s
user 1m28.866s
sys 0m3.192s

[root@venu ]# time sh primefactors.sh 99999999000000000
Prime Factors of 99999999000000000: 2x2x2x2x2x2x2x2x2x3x3x5x5x5x5x5x5x5x5x5x11x7
3x101x137

real 0m0.543s
user 0m0.508s
sys 0m0.035s

6 comments:

  1. Hi Friends ,
    Prime numbers are the best way through this .Finding prime numbers can be find through it .

    ReplyDelete
  2. That's cool, I still can't figure out how the script is doing it though. :P

    ReplyDelete
  3. Just a note the factor command also does the same. This comes with the standard coreutils package.

    ReplyDelete
  4. This is rally nice article, it helped me out.

    Thank you very much.

    QuickBooks Hosting

    ReplyDelete
  5. I am getting this error while executing the above program. Is any correction needed in it?

    ~$ sh primefactors.sh 812
    primefactors.sh: 37: primefactors.sh: Syntax error: Bad for loop variable

    ReplyDelete
  6. Very nice solution
    for formate pendrive in linux
    www.cloudwalks.com

    ReplyDelete