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

## Friday, June 24, 2011

### Shell Script to Find Prime Factors of a Number

Subscribe to:
Post Comments (Atom)

Hi Friends ,

ReplyDeletePrime numbers are the best way through this .Finding prime numbers can be find through it .

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

ReplyDeleteJust a note the factor command also does the same. This comes with the standard coreutils package.

ReplyDeleteThis is rally nice article, it helped me out.

ReplyDeleteThank you very much.

QuickBooks Hosting

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

ReplyDelete~$ sh primefactors.sh 812

primefactors.sh: 37: primefactors.sh: Syntax error: Bad for loop variable

Very nice solution

ReplyDeletefor formate pendrive in linux

www.cloudwalks.com