+ 1

How can u write program for finding gcd of two numbers?

by using c language

6th Oct 2018, 11:31 AM
Saiteja Chitti
13 Respostas
- 2
#include<stdio.h> int main() { int a,b,t; printf("enterthevaluesa,b"); scanf("%d\n%d",&a,&b); while(a<b) { t=a; a=b; b=t; } {while (!(b==0)) { t=a; a=b; b=t%b; } } {printf("gcdofa,b is %d",a) } return 0; }
6th Oct 2018, 12:02 PM
Saiteja Chitti
+ 3
Use the Euclidean Algorithm: https://en.m.wikipedia.org/wiki/Euclidean_algorithm#Description In the Implementation section, you'll find a pseudocode too!
6th Oct 2018, 11:44 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 3
It shouldn't be too hard to translate Wikipedia's pseudocode into C, which is function gcd(a, b) while b ≠ 0 t := b; b := a mod b; a := t; return a; If you show me your attempt, I'll be more than happy to guide you.
6th Oct 2018, 11:51 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 3
int a, b; scanf("%d %d", &a, &b); while(b^=a^=b^=a%=b); printf("GCD is %d", a);
6th Oct 2018, 12:53 PM
Flandre Scarlet
Flandre Scarlet - avatar
+ 2
#include<stdio.h> int main() { int a,b,t; printf("enterthevaluesa,b"); scanf("%d\n%d",&a,&b); while(a<b) { t=a; a=b; b=t; } {while (!(b==0)) { t=a; a=b; b=t%b; } } {printf("gcdofa,b is %d",a) } return 0; }
6th Oct 2018, 12:01 PM
Saiteja Chitti
+ 2
Kirk Schafer made it a little shorter😆
6th Oct 2018, 1:31 PM
Flandre Scarlet
Flandre Scarlet - avatar
+ 2
Kishalaya Saha and now is the shortest i think i can do😆
6th Oct 2018, 1:36 PM
Flandre Scarlet
Flandre Scarlet - avatar
+ 1
there's probably a better way, but what came to mind for me was dividing each denominator by 2 until there is a list of prime numbers for each denominator. I would compare the lists. The sum of the compared results should equal the gcd. Best of luck to you.
6th Oct 2018, 11:48 AM
Steven M
Steven M - avatar
+ 1
Kishalaya Saha you're correct the mod operator takes care of this easily 😀
6th Oct 2018, 12:02 PM
Steven M
Steven M - avatar
+ 1
Steven M , it's actually a very clever algorithm, and is sometimes called the "(successive) division method". Many schools teach it too!
6th Oct 2018, 12:11 PM
Kishalaya Saha
Kishalaya Saha - avatar
0
do it by using c language
6th Oct 2018, 11:45 AM
Saiteja Chitti
0
no write program in c
6th Oct 2018, 11:49 AM
Saiteja Chitti
0
Ah, Flandre Scarlet , I'd almost forgotten that cool XOR swap trick! Thanks! 😄
6th Oct 2018, 1:28 PM
Kishalaya Saha
Kishalaya Saha - avatar