Finding the GCD in C++ Program

[nram2323]

Can someone write a quick program for me. The purpose of the program is to find the GCD(Greatest Common Denominator) of two integers that are inputed. All common denominators have to be displayed. Then at the end of the output, the greatest will be displayed. It will look something like this:

Numbers inputed:

20, 16

Common Denominators: 1,2,4
Greatest Common Denominator: 4

[CheesyBeefy]

Read the rules... We will not code things for you, and this is 100% likely to be a homework assignment. We aren't just a forum that spits out your homework so you can get a good grade, this is a helping website. At least ATTEMPT to do your own work then we might consider helping you.

[nram2323]

Well im sorry. Im new to this. Ill write what i can with what ive learned so far. I cant experiment with the program because i dont have the C++ program here at home. It is a school where i have Computer Science as a class.

[o0OpsyphiO0o]

Here's an idea of how you can do it :). Find the results generated by dividing the numerical input by a loop of values that decrement from the value until half of the numerical input. Make another loop that decrements a single unit from each of these results, if the result of the new loop ever turns up a value of 0, then you have yourself a denominator. Store the reults that return true to being a denomiator for all inputted numbers. Check the new results from both inputs against eachother to find the common denominators, find the highest common denominator.

[firedraco]

What OS/what program do you use at school/home?

[nram2323]

Microsoft Vision C++

[nram2323]

well ive started out basic

#include<iostream.h>
#include<iomanip.h>
#include<math.h>
int main()

{

int x=0;
int y=0;

cout<<"Please enter two integers"<<endl;
cin>>x;
cin>>y;

if ((x<0)||(y<0))
{
cout<<"Cannot use Negative Integers"<<endl;
cout<<"Please enter positive integers"<<endl;
cin>>x;
cin>>y;

for(y=x;y<=x;--y)
if(x%y=0)
cout<<y<<endl;

should it look sumthing like that?

[jsmith]

No.

I suggest you get yourself a free C++ compiler for home use.

I also suggest having a look at:

http://en.wikipedia.org/wiki/Greatest_common_divisor

which gives you the algorithm you need to compute the GCD (you'll need to look up the algorithm for LCM to do this).

[Scipio]

http://www.bloodshed.net/

Takes maybe a few minutes ;)

[jsmith]

Actually, I'm wrong... you don't need LCM; rather, you need to use Euclid's algorithm to find the GCD directly.

Here's a templated version that can find the GCD of constants known at compile time. You just need to convert this to a function that can take values at run time and do the same calculation.

#include <iostream>

template< size_t A, size_t B >
struct GCD {
    enum { value = GCD< B, A % B >::value };
};

template< size_t A >
struct GCD<A,0> {
    enum { value = A };
};

int main() {
    std::cout << "GCD( 12, 18 ) = " << GCD<12, 18>::value << std::endl;
}

Now you write:

int gcd( int a, int b ) {
  // ...  Hint: on the above Wiki page, click on Euclid's algorithm and it will give
  // you pseudo-code for the if-else you need.
}

[Somelauw]

well ive started out basic

#include<iostream.h>
#include<iomanip.h>
#include<math.h>
int main()

{

int x=0;
int y=0;

cout<<"Please enter two integers"<<endl;
cin>>x;
cin>>y;

if ((x<0)||(y<0))
{
cout<<"Cannot use Negative Integers"<<endl;
cout<<"Please enter positive integers"<<endl;
cin>>x;
cin>>y;

for(y=x;y<=x;--y)
if(x%y=0)
cout<<y<<endl;

should it look sumthing like that?

1. Please use code tags + indention
2. For checking input a do ... while can be used.
3. Where did you get that algoritmn from? It's not correct. Find a working algoritmn and convert it to C++.

The simplest but not fastest algoritmn is to keep subtracting the lowest number from the highest one until you get zero.
Then return the value of the former lowest number. (The former highest one became zero)

[grcunning]

here's a hint, I won' t write the code for you:

the GCD of x and y is y if x mod y is 0

otherwise the GCD is the GCD of y and the remainder of x/y

look for recursive functions in your textbook, gcd is one of the simplest ones to write and understand.