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] ...
#checking whether atleast two numbers are provided
#assigning values to array a and finding smallest number
# assigning values to null positional parameters to avoid error
#finding hcf
-------------------------------------------------------------------------------------------
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
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
#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
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
if [ "$2" == "$null" ]; then
echo -e "\e[1;31mAtleast two numbers required !!\e[0m"
exit 0
fi
while [[ $# -gt 0 ]];do
a[$b]=$1;
b=$((b + 1))
if [ $1 -lt $d ];then
d=$1
fi
count=$((count + 1))
shift
done
for (( c=9; c>$count; c-- ));do
a[$c]=$d
done
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
This comment has been removed by a blog administrator.
ReplyDelete