Find hcf ( highest common factor )

Script to find hcf ( highest common factor )

In mathematics , the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.
                                                       -wikipeda http://en.wikipedia.org/wiki/Highest_common_factor )


1.
-------------------------------------------------------------------------------------------------------------------------------------------------
HOW THIS SCRIPT WORKS:
In this script all given values are tested for divisibility simultaneously with natural numbers from 2 to the smallest given value i.e if we try to find hcf of 60 and 600000; this script will check divisibilty of 60 and 600000 simultaneously by natural numbers from 2 to 60 to find the hcf.
-------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------
#!/bin/bash

#to find the highest common factor (hcf) of two or more numbers (maximum 9)
#usage hcf [number] [number] ...

b=1
d=1000000000000

#checking whether atleast two numbers are provided
if [ "$2" == "$null" ]; then 
    echo -e "\e[1;31mAtleast two numbers required !!\e[0m
    exit 0
fi

#assigning values to array a and finding smallest number
while [[ $# -gt 0 ]];do  
     a[$b]=$1;
     b=$((b + 1))
     if [ $1 -lt $d ];then
         d=$1
     fi
     count=$((count + 1))
     shift
done

# assigning values to null positional parameters to avoid error
for (( c=9; c>$count; c-- ));do  
    a[$c]=$d
done 

#finding hcf
for (( i=2; i<=$d; i++ ));do 
     if (( $(( ${a[1]} % $i )) == 0 && $(( ${a[2]} % $i )) == 0  && $(( ${a[3]} % $i )) == 0 && $(( ${a[4]} % $i )) == 0 && $(( ${a[5]} % $i )) == 0 && $(( ${a[6]} % $i )) == 0 && $(( ${a[7]} % $i )) == 0 && $(( ${a[8]} % $i )) == 0 && $(( ${a[9]} % $i )) == 0 ));then
         echo -e "h.c.f = \e[1;34m$i\e[0m"         
         exit 0
     fi
done
echo -e "h.c.f = \e[1;34m1\e[0m"




-------------------------------------------------------------------------------------------

In my system the script is named hcf . If you want to find h.c.f of say 4, 8, 56 then in terminal type hcf 4 8 56 and just press Enter..






things I noticed about this script : 
* when higher values are given it will take a little more time
* maximum 9 values only in one calculation 




2.
-------------------------------------------------------------------------------------------------------------------------------------------------
HOW THIS SCRIPT WORKS:
This script is based on Fundamental Theorem of Arithmetic : Every composite number can be expressed ( factorised ) as a product of primes, and this factorisation is unique, apart from the order in which the prime factors occur.
Each number is factorised and then common factors are taken and multiplied to get hcf. For example
when finding hcf of 8 and 12
factors of 8= 2 2 2
factors of 12=2 2 3
Taking common factors and multiplying we get 2 x 2 =4
Hence hcf=4
-------------------------------------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------

#!/bin/bash

# find hcf of numbers
#usage hcf [number] [number] ...

#checking whether atleast two numbers are provided
if [ "$2" == "$null" ]; then 
    echo -e "\e[1;31mAtleast two numbers required !!\e[0m
    exit 0
fi

largestfactor=0
count=1
totalnum=$#

#finding factors of each number and assigning to array factor
#finding largest factor value
while [ $# -gt 0 ];do
     num=$1
     savenum=$1
     for (( i=2; i<=$savenum; i++ ));do
         while [ $((num%$i)) == 0 ];do
             factor[$count]="${factor[$count]} $i"
             if [ $i -gt $largestfactor ];then
                 largestfactor=$i
             fi
             num=$((num/$i))
         done 
     done
     shift
     count=$((count + 1))
done

hcf=1
exponent=10000000

#finding hcf
for (( i=2; i<=$largestfactor; i++ ));do
    for (( k=1; k<=$totalnum; k++ ));do
        if [[ $(echo ${factor[$k]} | grep -w -o $i | wc -l) -lt $exponent ]];then
             exponent=$(echo ${factor[$k]} | grep -w -o $i | wc -l)
        fi
    done
    hcf=$((hcf*(i**exponent)))
    exponent=100000000
done

echo -e "h.c.f = \e[1;34m$hcf\e[0m"

-------------------------------------------------------------------------------------------
Usage is same as the first script.


things I noticed about this script : 
* when higher values are given it will take very long time for the result
* unlimited number of values in one calculation 





3.
-------------------------------------------------------------------------------------------------------------------------------------------------
HOW THIS SCRIPT WORKS:
This script is based on Euclid's Division Lemma : Given positive integers a and b, there exist unique integers q and r satisfying a=bq+r, 0< r <b.
If you want to find hcf of 455 and 42, starting with larger value and applying the division lemma 
455=42 x 10 +35
now consider the divisor 42 and the reminder 35 and apply the division lemma
42=35 x 1 +7
now consider the divisor 35 and the reminder 7 and apply the division lemma
35=7 x 5 + 0
reminder is now zero.Hence hcf of 455 and 42 is 7

-------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------

#!/bin/bash

#for finding hcf of two numbers only
#usage hcf [number] [number]

#checking whether two numbers are provided
if [ "$2" == "$null" ]; then 
    echo -e "\e[1;31mTwo numbers required !!\e[0m
    exit 0
fi

#finding the highest value
if [[ $1 -eq $2 ]];then
   echo -e "h.c.f = \e[1;34m$1\e[0m"
   exit 0
elif [[ $1 -gt $2 ]];then
   greater=$1
   lower=$2
else
   greater=$2
   lower=$1
fi

#finding hcf
while [ $lower -ne 0 ];do
    hcf=$lower
    lower=$((greater%lower))
    greater=$hcf
done

echo -e "h.c.f = \e[1;34m$hcf\e[0m"

-------------------------------------------------------------------------------------------
Usage is same as the first script.


things I noticed about this script : 
give instant result even with higher values
* only two values in one calculation 

Enjoy Linux!!

Dont know what to do with these codes ?? click here

1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete