hcf and lcm

[sailee]

Pls help me in finding hcf and lcm of 2 nos

[Ancient Dragon]

Pls help me in finding hcf and lcm of 2 nos

What the hell does that mean :angry:

[Narue]

>Pls help me in finding hcf and lcm of 2 nos
It's easy. All you do is grab the igm, do a qp on the xt half of the pgid and roll everything up into a qt7-qualified czsm. Hope that helps! :)

[Salem]

> Pls help me in finding hcf and lcm of 2 nos
Have you tried looking down the back of the sofa?
That's where I usually find things.

[hammerhead]

Okay here is the pseudo code for hcf, credit to Euclid.

gcd(m,n)

r<-(m MOD n);
if r=0 then
  { return n }
else
{
m<-n
n<-r
gcd(m,n)
}

Sorry if my pseudocode is not as per standard.

[mitrmkar]

Okay here is the pseudo code for hcf, credit to Euclid.

Umm, I think I got the hcf part of it (thanks hammerhead), but how to figure out 'lcm of 2 nos' just beats me :-/ ...

[hammerhead]

LCM is the tricky one. One needs to know that every number greater than 1 can be represented as products of prime numbers. Once factors each number m,n into its corresponding prime factors and then by multiplying the numbers with highest order we get the LCM. I have never implemented it on C++, it would be a good idea to do it now :D

Here are some links on LCM
http://mathworld.wolfram.com/LeastCommonMultiple.html
http://en.wikipedia.org/wiki/Least_common_multiple

[hammerhead]

Umm, I think I got the hcf part of it (thanks hammerhead), but how to figure out 'lcm of 2 nos' just beats me :-/ ...

Also note how m and n get interchanged if n>m, consider the case of m=6 and n=15

r1=6 MOD 15 = 6

m<-n implies m=15
n<-r implies n=6

the process is repeated to get gcd as 3

[mitrmkar]

the process is repeated to get gcd as 3

Ermm, so eventually everything rolls up into a "qt7-qualified czsm" (?)

[bugmenot]

note that with any two numbers a and b, a * b = gcd(a, b) * lcm(a, b)

[sailee]

pls could you do it by void main....
i m only a kid....

[sailee]

Ermm, so eventually everything rolls up into a "qt7-qualified czsm" (?)

I m just a 14 yr old kid who has been taught d basics....:icon_redface:
so pls help me do it in void main or my prof wil hang me upside-down....:sad:

[Prabakar]

I dont like to use recursion, unless it is very much necessary. If i were to calcualte GCD between 2 numbers, I would do it somthing like this.

#define min(a, b) (a)<(b)?(a):(b)
int main ( )
{
    int a, b, i, c, d, gcd = 1, lcm ;
    cin >> a >> b ;
    c = a ; d = b ;
    for ( i = min(a, b) ; i > 1 ; i-- )
         if ( a % i == 0 && b % i == 0 )
         {
              gcd = gcd * i ;
              a = a / i ;
              b = b / i ;
              i = min ( i, min ( a, b ) );
          }
    lcm = c / gcd * d;
    cout << gcd << lcm ;
}

[Radical Edward]

> I dont like to use recursion, unless it is very much necessary
Don't fear recursion, it's cool! ;) Actually, Ed doesn't use recursion either unless it makes the code much shorter or simpler. It's a great tool if you know when to use it and more importantly, when not to use it.

[jephthah]

this thread made me laugh.

[hk<3ob1993]

Umm, I think I got the hcf part of it (thanks hammerhead), but how to figure out 'lcm of 2 nos' just beats me :-/ ...

lcm is the easy part
theres a property in maths:
for to number x and y

hcf(x,y) * lcm(x,y) = x*y

just divide the product of the 2 numbers by the hcf ... u have ur lcm