.

Labels

.

Find LCM

Script for finding LCM ( least common multiple )

In arithmetic and number theory , the least common multiple (also called the lowest common multiple or smallest common multiple) of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is a multiple of both a and b. It is familiar from grade-school arithmetic as the "lowest common denominator" that must be determined before two fractions can be added.  
                                               - wikipedia ( http://en.wikipedia.org/wiki/Least_common_multiple )


1.

-------------------------------------------------------------------------------------------------------------------------------------------------
HOW THIS SCRIPT WORKS:
In this script  natural numbers starting from the greatest value given is tested simultaneously for divisibility by the given values i.e when finding lcm of 3 and 4 , natural numbers from 4,5,6... are tested  
till lcm is obtained.
-------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------
#!/bin/bash

#to find the least common multiple (lcm) of numbers (maximum 9)

#checking whether there is any number provided
if [[ $1 == $null ]];then
    echo -e "\e[1;31mAtleast one number is needed!!\e[0m"
    exit 0
fi 

#for assigning values to array b and finding highest number given 
count=$#
k=1
a=$1
while [[ $# -gt 0 ]];do
    if [[ $1 > $2 ]];then
         a=$1
    fi
b[$k]=$1
k=$k+1
shift
done

#putting values to other positional parameters 
lcm=0
for (( c=9; c>$count; c-- ));do
    b[$c]=1
done 
#finding lcm
for (( i=$a; i>=$a; i++ ));do
    if (( $(($i % ${b[1]})) == 0 && $(($i % ${b[2]})) == 0 && $(($i % ${b[3]})) == 0 && $(($i % ${b[4]})) == 0 && $(($i % ${b[5]})) == 0 && $(($i % ${b[6]})) == 0 && $(($i % ${b[7]})) == 0 && $(($i % ${b[8]})) == 0 && $(($i % ${b[9]})) == 0 ));then
           echo -e "l.c.m = \e[1;34m$i\e[0m"
           exit 0           
    fi
done

-------------------------------------------------------------------------------------------
In my system the script is named lcm. To find the lcm of 2 ,6 ,9 and 13 ; in terminal type lcm 2 6 9 13  press enter ..






things I noticed about this script : 
* when more and higher values are given it will take very long time for result
* maximum 9 values only in one calculation  




2.

-------------------------------------------------------------------------------------------------------------------------------------------------
HOW THIS SCRIPT WORKS:
Script uses prime factorization method to find lcm. For example for finding lcm of 4 and 6
factors of 4=2 2
factors of 6=2 3
taking common factors only ones and multiplying with all the other factors we get
2x2x3=12
hence lcm=12
-------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------

#!/bin/bash

# find lcm of numbers
#usage lcm [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 ];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

lcm=1
exponent=0

#finding lcm
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
    lcm=$((lcm*(i**exponent)))
    exponent=0
done

echo -e "l.c.m" = \e[1;34m$lcm\e[0m"




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


things I noticed about this script : 
* even when more and higher values are given result is obtained fast
* unlimited number of values in one calculation


Enjoy Linux !! 

Don't know what to do with these codes ??  click here

No comments:

Post a Comment