C++

Forum

 
GCD

Kairi (6)
the greatest common divisor of two integers n1 and n2 is as follows: first find d to be the minimum of n1 and n2, then check whether d, d-1, d-2,....,2, or 1 is a divisor for both n1 and n2 in this order. The first such common divisor is the greatest common divisor for n1 and n2.

Here is what I have.
I don't know what to do after this.

#include<iostream>
#include<iomanip>
#include<cmath>

using namespace std;

int main()

{
int n1;
int n2;
int gcd = 1;
int k = 2;

cout << "Enter the fist integer:";
cin >> n1;
cout << "Enter the second integer:";
cin >> n2;



while (k <= n1 && k <= n2)
{
if (n1 % k == 0 && n2 % k == 0)
gcd = k;
k++;
}
cout << "The greatest common divisor for "<< n1 <<" and " << n2 << " is "<< gcd<<endl;

return 0;
}

Could someone please show me what the program is supposed to look like.
Thanks in Advance.

Ps. GCD-Greatest Common Divisor
Last edited on
Duthomhas (13206)
What you have works fine. As you learn more you'll be able to write problems like this much better... but you have correctly solved your assignment.

Hope this helps.
Kairi (6)
I showed this to my teacher and she said it was supposed to be solved in a different way than how I solved it.

Could someone please show me a different way to solve it, and make sure it loops.
Thanks.
yoked88 (140)
I am new and I created a fraction calculator that is very basic, the main concept behind it was to pass lots of parameters and to keep variables out of main.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
#include <iostream>

using namespace std;

void menuFunction();
void addFraction(int, int, int, int, int&, int&);
void subtractFraction(int, int, int, int, int&, int&);
void multiplyFraction(int, int, int, int, int&, int&);
void divideFraction(int, int, int, int, int&, int&);

int main()
{
	menuFunction();
	return 0;
}

void menuFunction()
{
	int choice, num1, num2, denom1, denom2, numResult = 0, denomResult = 0;
	cout<<"This program lets you perform operations on fractions."<<endl;
	cout<<"Input data as (a/b) and (c/d), then select an operation to perform."<<endl<<endl;
	cout<<"Operation                Number"<<endl;
	cout<<"-------------------------------"<<endl;
	cout<<"Adding fractions:           1"<<endl;
	cout<<"Subtracting fractions:      2"<<endl;
	cout<<"Multiplying fractions:      3"<<endl;
	cout<<"Dividing fractions:         4"<<endl;
	cout<<"-------------------------------"<<endl;
	cout<<"\nEnter fractions:  "<<endl;
	cin>>num1>>denom1>>num2>>denom2;
	cout<<"Enter operation (number):   "<<endl;
	cin>>choice;
	cout<<endl;
	switch(choice)
	{
	case 1:
		addFraction(num1, denom1, num2, denom2, numResult, denomResult);
		break;
	case 2:
		subtractFraction(num1, denom1, num2, denom2, numResult, denomResult);
		break;
	case 3:
		multiplyFraction(num1, denom1, num2, denom2, numResult, denomResult);
		break;
	case 4:
		divideFraction(num1, denom1, num2, denom2, numResult, denomResult);
		break;
	default:
		cout<<"\nInvalid input.\n"<<endl;
	}
	cout<<"Result = "<<numResult<<"/"<<denomResult<<endl;
}

void addFraction(int top1, int bottom1, int top2, int bottom2, int& topResult, int& bottomResult)
{
	if(bottom1 != 0 && bottom2 != 0)
	{
	    int numerator1 = (bottom1 * bottom2) / bottom1;
	    int numerator2 = (bottom1 * bottom2) / bottom2;
	    bottomResult = bottom1 * bottom2;
	    int newNum1 = numerator1 * top1;
	    int newNum2 = numerator2 * top2;
	    topResult = newNum1 + newNum2;
	}
	else
		cout<<"\nInvalid input, denominator cannot be 0."<<endl;
}

void subtractFraction(int top1, int bottom1, int top2, int bottom2, int& topResult, int& bottomResult)
{
	if(bottom1 != 0 && bottom2 != 0)
	{
		int numerator1 = (bottom1 * bottom2) / bottom1;
		int numerator2 = (bottom1 * bottom2) / bottom2;
		bottomResult = bottom1 * bottom2;
		int newNum1 = numerator1 * top1;
		int newNum2 = numerator2 * top2;
		topResult = newNum1 - newNum2;
	}
	else
		cout<<"\nInvalid input, denominator cannot be 0."<<endl;
}

void multiplyFraction(int top1, int bottom1, int top2, int bottom2, int& topResult, int& bottomResult)
{
	if(bottom1 != 0 && bottom2 != 0)
	{
		bottomResult = bottom1 * bottom2;
		topResult = top1 * top2;
	}
	else
		cout<<"\nInvalid input, denominator cannot be 0."<<endl;
}

void divideFraction(int top1, int bottom1, int top2, int bottom2, int& topResult, int& bottomResult)
{
	if(bottom1 != 0 && bottom2 != 0)
	{
	    int newTop = bottom2;
	    int newBottom = top2;
	    topResult = top1 * newTop;
	    bottomResult = bottom1 * newBottom;
	}
	else
		cout<<"\nInvalid input.\n"<<endl;
}
jsmith (5804)
Wikipedia gives many algorithms for computing GCD and LCM much more efficiently than the above while loop.
Look up "GCD".
Duthomhas (13206)
@Kairi
Your teacher is not being helpful to just say "I wanted a different answer." Your answer is both correct and complies with the requirements.

The only trick is that you did it backwards. :-)

Your loop goes from d-n,..,d-1,d and calculates every common divisor, instead of d,d-1,..,d-n and stopping at the first CD found.

Start by calculating the minimum of n1 and n2:
1
2
 
if (n1 < n2) d = n1;
else         d = n2;

Now you can write a loop where d-n, for n in 0,1,2,3... solves the equation. I would do like you did above where you have the identity k = d-n for each n.
3
4
5
6
7
 
for (k = d; k > 1; k--)
  {
  if (n1 % k == 0 && n2 % k == 0)
    gcd = k;
  }

The only trick, now, is that once you find the first GCD, you can stop the loop:
3
4
5
6
7
8
9
10
 
for (k = d; k > 1; k--)
  {
  if (n1 % k == 0 && n2 % k == 0)
    {
    gcd = k;
    break;
    }
  }

Hope this helps.

@yoked88
What? That has nothing to do with solving the GCD.
Last edited on
Topic archived. No new replies allowed.