How to resolve the algorithm Least common multiple step by step in the UNIX Shell programming language

Published on 12 May 2024 09:40 PM
#Unix shell

How to resolve the algorithm Least common multiple step by step in the UNIX Shell programming language

Table of Contents

Problem Statement

Compute the   least common multiple   (LCM)   of two integers. Given   m   and   n,   the least common multiple is the smallest positive integer that has both   m   and   n   as factors.

The least common multiple of   12   and   18   is   36,       because:

As a special case,   if either   m   or   n   is zero,   then the least common multiple is zero.

One way to calculate the least common multiple is to iterate all the multiples of   m,   until you find one that is also a multiple of   n. If you already have   gcd   for greatest common divisor,   then this formula calculates   lcm.

One can also find   lcm   by merging the prime decompositions of both   m   and   n.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Least common multiple step by step in the UNIX Shell programming language

Source code in the unix programming language

gcd() {
	# Calculate $1 % $2 until $2 becomes zero.
	until test 0 -eq "$2"; do
		# Parallel assignment: set -- 1 2
		set -- "$2" "`expr "$1" % "$2"`"
	done

	# Echo absolute value of $1.
	test 0 -gt "$1" && set -- "`expr 0 - "$1"`"
	echo "$1"
}

lcm() {
	set -- "$1" "$2" "`gcd "$1" "$2"`"
	set -- "`expr "$1" \* "$2" / "$3"`"
	test 0 -gt "$1" && set -- "`expr 0 - "$1"`"
	echo "$1"
}

lcm 30 -42
# => 210


alias gcd eval \''set gcd_args=( \!*:q )	\\
	@ gcd_u=$gcd_args[2]			\\
	@ gcd_v=$gcd_args[3]			\\
	while ( $gcd_v != 0 )			\\
		@ gcd_t = $gcd_u % $gcd_v	\\
		@ gcd_u = $gcd_v		\\
		@ gcd_v = $gcd_t		\\
	end					\\
	if ( $gcd_u < 0 ) @ gcd_u = - $gcd_u	\\
	@ $gcd_args[1]=$gcd_u			\\
'\'

alias lcm eval \''set lcm_args=( \!*:q )	\\
	@ lcm_m = $lcm_args[2]			\\
	@ lcm_n = $lcm_args[3]			\\
	gcd lcm_d $lcm_m $lcm_n			\\
	@ lcm_r = ( $lcm_m * $lcm_n ) / $lcm_d	\\
	if ( $lcm_r < 0 ) @ lcm_r = - $lcm_r	\\
	@ $lcm_args[1] = $lcm_r			\\
'\'

lcm result 30 -42
echo $result
# => 210

You may also check:How to resolve the algorithm Balanced ternary step by step in the Wren programming language
You may also check:How to resolve the algorithm Subtractive generator step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Identity matrix step by step in the Ring programming language
You may also check:How to resolve the algorithm Call a function step by step in the XSLT programming language
You may also check:How to resolve the algorithm Soundex step by step in the Crystal programming language