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 <positive integer="">
[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