` `

```
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