Computer Science Canada

LowestCommonMultiple
Author:  Viper [ Thu Nov 10, 2005 1:57 pm ]
Post subject:  LowestCommonMultiple
**Recursion must be used**
The LCM (lowest common multiple ) of two non-zero integers can be found using the formula: lcm(num1, num2) = num1*num2/ gcd(num1, num2) where: gcd(num1, num2) is the greatest common divisor of num1 and num2. here's the trick. the program should employ a recursive approach to finding the gcd of two number. The recursive definition is given by:
if num2 divides evenly into num1 then
gcd= num2

could someone re-write tht in C++ for me plz Very Happy

here it is in turing
code:
var lcm, gcd : real := 0
var num1, num2 : int := 0
%------------------------------------------------------------------------------------------
proc starter
    put "Enter the numbers you wish to find the 'LCM' for"
    put "***********Hit enter after each number**********"
    get num1
    get num2
end starter
%------------------------------------------------------------------------------------------
proc GCD (num1, num2 : real)
    if num1 mod num2 = 0 then
        gcd := num2
    else
        GCD (num2, num1 mod num2)
    end if
end GCD
%------------------------------------------------------------------------------------------
proc LCM (gcd, num1, num2 : real)
    lcm := num1 * num2 / gcd
    put "The 'LCM' for", " ", num1, " ", "&", " ", num2, " ", "is", " ", lcm
    put "The 'GCD' for", " ", num1, " ", "&", " ", num2, " ", "is", " ", gcd
end LCM

%MAIN-----------------------------------
starter
GCD (num1, num2)
LCM (gcd, num1, num2)
Author:  [Gandalf] [ Thu Nov 10, 2005 4:17 pm ]
Post subject: 
No. Try it yourself first.
Author:  Geminias [ Fri Nov 11, 2005 6:12 pm ]
Post subject:  hey
here you go Razz



syntax = c++
code:

#include <iostream>

void intro ();
float module ();
float lcm (float GCD);
void intro ()
{
     int num1 = 0, num2 = 0, N1 = 0, N2 = 0;
     int *pNum1 =  num1;
     int *pNum2 =  num2;
     int *pN1 =  N1;
     int *pN1 =  N2;
     
     
     std::cout << "Enter the numbers you wish to find the LCM for" << std::endl  <<
     "********Hit enter after each number*********<< std::endl << std::endl;
     
     std::cin >> num1;
     std::cin >> num2;
     N1 = num1;
     N2 = num2;
}

float module ()
{
      float gcd;
 
     if (*pNum1 % *pNum2 == o)
   {
        gcd = *pNum2;
   }
     else
   {   
       *pNum1 = *pNum2;
       *pNum2 = *pNum1 % *pNum2;
       module ();
   }
   
   return gcd;
}

float lcm(float GCD)
{
      lcm = *pNum2 * (*pNum1) / GCD;
      return lcm;
}

int main ()
{
    intro();
    std::cout << "The LCM for " << *pN1 << " and " << *pN2 << " is " << lcm (module()) << std::endl;
    std::cout << "The GCM for " << *pN1 << " and " << *pN2 << " is " << lcm (module()) << std::endl;
   



Author:  wtd [ Fri Nov 11, 2005 6:25 pm ]
Post subject: 
Wow...

c++:
float module ()
{
   float gcd;
 
   if (*pNum1 % *pNum2 == o)
   {
      gcd = *pNum2;
   }
   else
   {   
      *pNum1 = *pNum2;
      *pNum2 = *pNum1 % *pNum2;
      module ();
   }
   
   return gcd;
}


Where do you think pNum1 and pNum2 are coming from? I don't see a declaration for them in the function. Nor do I see a declaration for them in the global scope.

c++:
std::cout << "Enter the numbers you wish to find the LCM for" << std::endl
     "********Hit enter after each number*********<< std::endl << std::endl;


You have this, which makes no sense, since you're missing an insertion operator.

You don't have a closing brace at the end of "main".

Is there any particular reason you thought this code would work?
Author:  Geminias [ Fri Nov 11, 2005 6:36 pm ]
Post subject: 
yeah i honestly thought pointers would last forever until i deleted them lol

i just tested and realized they don't...

plus yeah there is a whole score of syntax errors
Author:  wtd [ Fri Nov 11, 2005 6:39 pm ]
Post subject: 
Research the concept of "scope".
Author:  Geminias [ Fri Nov 11, 2005 8:29 pm ]
Post subject: 
i think i understand scope but i misunderstood how a pointer works. i thought the specific purpose of a pointer was to access private data. Which, maybe it is, but i should declare the pointers as global. i'll check as soon as i have time
Author:  wtd [ Fri Nov 11, 2005 8:36 pm ]
Post subject: 
Geminias wrote:
i think i understand scope but i misunderstood how a pointer works. i thought the specific purpose of a pointer was to access private data. Which, maybe it is, but i should declare the pointers as global. i'll check as soon as i have time


No, you should not declare variables (a pointer is just a variable) globally. Learn how to pass things via arguments.
Author:  Geminias [ Sat Nov 12, 2005 11:46 am ]
Post subject:  heyho
hey again, yeah i dropped out the idea of pointers and functions for this.
it finds the lowest common multiple and the highest common multiple (LCM) (GCM) but it excludes 1. Because 1 divides into everything.
in the case that only one number besides 1 is common to both numbers, then LCM = GCM.

Viper, your recursion technique did not work. It does not find the LCM and GCM.

try this.... (note: if one of the numbers is prime the program crashes.)

syntax = c++
code:
#include <iostream>

int main ()
{
    unsigned long int num1, num2, gcm,lcm;
    std::cout << "Enter two numbers starting with the highest one." << std::endl <<
    "*********hit enter after each number**************" << std::endl << std:: endl;
   
    std::cin >> num1;
    std::cin >> num2;
    gcm = 1;
    for (int i = num2; i >= gcm ; i--)
  {
        if (num2 % i == 0 && num1 % i == 0)
     {   gcm = i; 
     }
     else if (i = 1)
    {   
        gcm = 1
     }

  }
     for (int i = 2; i <= num2; i++)
   {
         if (num2 % i == 0 && num1 % i ==0)
         {
              lcm = i;
              i = num2;
         }
         else if (i = num2)
        {
             lcm = 1;
         }
   }

   std::cout << "The LCM is: " << lcm << std::endl;
   std::cout << "The GCM is: " << gcm << std::endl;
   std::cin.ignore(1,'\n');
   std::cin.ignore();
   
 
   return 0;
}       
   
Author:  wtd [ Sat Nov 12, 2005 12:38 pm ]
Post subject: 
What is "Greatest Common Multiple"? Infinity?

code:
$ ./a.ut
Enter two numbers starting with the highest one.
*********hit enter after each number**************

4
3
The LCM is: 0
The GCM is: 1


For a cleaned up version of your code.

c++:
#include <iostream>

int main ()
{
    unsigned long int num1, num2, gcm,lcm;
    std::cout << "Enter two numbers starting with the highest one."   << std::endl
              << "*********hit enter after each number**************" << std::endl
              << std:: endl;
   
    std::cin >> num1;
    std::cin >> num2;
    gcm = 1;
   
    for (int i = num2; i > gcm ; i--)
    {
        if (num2 % i == 0 && num1 % i == 0)
        {
            gcm = i;
        }
    }
   
    for (int i = 2; i < num2; i++)
    {
        if (num2 % i == 0 && num1 % i ==0)
        {
            lcm = i;
            i = num2;
        }
    }

    std::cout << "The LCM is: " << lcm << std::endl;
    std::cout << "The GCM is: " << gcm << std::endl;
   
    return 0;
}
Author:  wtd [ Sat Nov 12, 2005 12:55 pm ]
Post subject: 
I'm not going to give you working C++ code for this, but I will show you the algorithm.

code:
# let rec gcd num1 num2 =
     if num1 > num2 then
        if num1 mod num2 = 0 then
           num2
        else
           gcd (num1 mod num2) num2
     else
        gcd num2 num1;;
val gcd : int -> int -> int = <fun>
# gcd 12 8;;
- : int = 4
# gcd 2336 1314;;
- : int = 146
# let lcm num1 num2 = num1 * num2 / gcd num1 num2;;
val lcm : int -> int -> int = <fun>
# lcm 57 12;;
- : int = 228
# 57 * 12;;
- : int = 684


You may also wish to hit Google. Never know what you'll find.
Author:  Geminias [ Sat Nov 12, 2005 1:35 pm ]
Post subject: 
i fixed the logic so it will return 1 as both lcm and gcm in the case that there are no other common multiples.

hey wtd, how do you get all that pretty color in your code lol
Author:  Andy [ Sat Nov 12, 2005 1:50 pm ]
Post subject: 
use code tags instead of [code ] use [sytax="cpp" ]
Author:  Geminias [ Sat Nov 12, 2005 3:16 pm ]
Post subject:  Re: heyho
Geminias wrote:
hey again, yeah i dropped out the idea of pointers and functions for this.
it finds the lowest common multiple and the highest common multiple (LCM) (GCM) but it excludes 1. Because 1 divides into everything.
in the case that only one number besides 1 is common to both numbers, then LCM = GCM.

Viper, your recursion technique did not work. It does not find the LCM and GCM.

try this.... (note: if one of the numbers is prime the program crashes.)

syntax = c++
c++:
#include <iostream>

int main ()
{
    unsigned long int num1, num2, gcm,lcm;
    std::cout << "Enter two numbers starting with the highest one." << std::endl <<
    "*********hit enter after each number**************" << std::endl << std:: endl;
   
    std::cin >> num1;
    std::cin >> num2;
    gcm = 1;
    for (int i = num2; i >= gcm ; i--)
  {
        if (num2 % i == 0 && num1 % i == 0)
     {   gcm = i; 
     }
     else if (i = 1)
    {   
        gcm = 1
     }

  }
     for (int i = 2; i <= num2; i++)
   {
         if (num2 % i == 0 && num1 % i ==0)
         {
              lcm = i;
              i = num2;
         }
         else if (i = num2)
        {
             lcm = 1;
         }
   }

   std::cout << "The LCM is: " << lcm << std::endl;
   std::cout << "The GCM is: " << gcm << std::endl;
   std::cin.ignore(1,'\n');
   std::cin.ignore();
   
 
   return 0;
}       
   
Author:  Geminias [ Sat Nov 12, 2005 3:17 pm ]
Post subject: 
thanks Laughing
Author:  [Gandalf] [ Sat Nov 12, 2005 4:04 pm ]
Post subject: 
So now you don't have to type syntax = c++ before your code, just do it inside the tags. You also don't have to double post because you can edit your posts. Even better, if you wanted to check if it works you could have used the preview button and edited your post before posting it Smile.
Author:  Geminias [ Sun Nov 13, 2005 7:53 pm ]
Post subject: 
lol, ya ya, i'm a big noob. laugh while you still can Razz
Author:  wtd [ Sun Nov 13, 2005 8:06 pm ]
Post subject: 
We're all noobs next to someone.
Author:  md [ Sun Nov 13, 2005 10:09 pm ]
Post subject: 
I disagree! I'm a noob next to everyone! Wait...

In any case it's alright to make mistakes, so long as you learn from them Smile
Author:  Flikerator [ Tue Nov 15, 2005 3:01 pm ]
Post subject: 
Cornflake wrote:
I disagree! I'm a noob next to everyone! Wait...

In any case it's alright to make mistakes, so long as you learn from them Smile


Except when sky diving...Its better to learn from other peoples mistakes Rolling Eyes Wink
Author:  bugzpodder [ Tue Nov 15, 2005 6:13 pm ]
Post subject:  Re: LowestCommonMultiple
Viper wrote:
**Recursion must be used**
The LCM (lowest common multiple ) of two non-zero integers can be found using the formula: lcm(num1, num2) = num1*num2/ gcd(num1, num2) where: gcd(num1, num2) is the greatest common divisor of num1 and num2. here's the trick. the program should employ a recursive approach to finding the gcd of two number. The recursive definition is given by:
if num2 divides evenly into num1 then
gcd= num2

could someone re-write tht in C++ for me plz Very Happy

here it is in turing
code:
var lcm, gcd : real := 0
var num1, num2 : int := 0
%------------------------------------------------------------------------------------------
proc starter
    put "Enter the numbers you wish to find the 'LCM' for"
    put "***********Hit enter after each number**********"
    get num1
    get num2
end starter
%------------------------------------------------------------------------------------------
proc GCD (num1, num2 : real)
    if num1 mod num2 = 0 then
        gcd := num2
    else
        GCD (num2, num1 mod num2)
    end if
end GCD
%------------------------------------------------------------------------------------------
proc LCM (gcd, num1, num2 : real)
    lcm := num1 * num2 / gcd
    put "The 'LCM' for", " ", num1, " ", "&", " ", num2, " ", "is", " ", lcm
    put "The 'GCD' for", " ", num1, " ", "&", " ", num2, " ", "is", " ", gcd
end LCM

%MAIN-----------------------------------
starter
GCD (num1, num2)
LCM (gcd, num1, num2)


gcd on reals? intriguing!! and I wouldnt do mod 0 if I were you. and be extra careful with negatives
Author:  MysticVegeta [ Thu Jan 19, 2006 12:25 pm ]
Post subject: 
Wow the recursive solution to the GCD and LCM using GCD is amazing.. Never thought about it really.. really neat website wtd, saving a shortcut in my programming folder.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy