Greatest Common Divider

Hi

I'm trying to calculate the greatest common divider.
But I guess there's something wrong with my algorythm to calculate it.

Help would be nice ^^.

Here's the code.

Code:

---

#include <stdio.h>
#include <conio.h>

void request (void);
void calculate (void);
int print (void);
int nra, nrb, ggd;


int main (void) {
        request();
        calculate();
        print();
}

void request(void){                                                       
    printf("Give in numbers for GCD: A B\n");
    scanf("%d %d", &nra, &nrb);
}

void calculate (void){
        if(nra==nrb)
                ggd=nra;
        else if ((nra>nrb) && (nra%nrb != 0))
                ggd=(nrb,nra%nrb);
                       
}

int print (void){
        printf("The greatest common divider of number A and number B is: %d\n", ggd);
        return ggd;
}

---

the only algorythm I got was this:




gcd(a,b)=a if a=b

gcd(a,b)=gcd(b,a%b) if a>b and a%b isn't 0

Code:

---

ggd=(nrb,nra%nrb);

---

is not syntactically correct.

yes I figured as much... but the problem is... I don't know the correct algorythm (I don't think that's the correct one for that purpose).. so I just fill it in like that.

I'm not exactly a mathematician :p

Go wiki "Euclidean algorithm".

I have done that. But I can't find a simple algorythm which I can implement in my program.
There are programming examples but I do not know how to use them. I have to use a recursive method. But it isn't anything like the program I made. Besides I don't really know how to use the "%"-operator. If anyone can help.. please do ^^ thx

recursive

Code:

---

int ggd(int a, int b){
  if(b==0){
    return a;
  }else{
    return ggd(b,a%b);
  }
}

---

iterative

Code:

---

int ggd(int a, int b){
  int rest;
  while(b != 0){
    rest=a%b;
    a=b;
    b=rest;
  }
  return a;
}

---

And what stops you from plugging either of those into calculate()?

tried that. gives all sorts of errors... :/ like: extraneous return value, unrecognized statement. expected this but found that.
and so on....

fixed it.. not with the recursive but the iterative way.. screw the task ^^

Code:

---

void calculate (void){
       
        int rest;
        while (nrb != 0){
                rest=nra%nrb;
                nra=nrb;
                nrb=rest;
        }
        ggd=nra;                       
}

---

Quote:

---

Originally Posted by nonoob

Code:

---

ggd=(nrb,nra%nrb);

---

is not syntactically correct.

---

To be pedantic: it is syntatically correct. It just do what the OP thought it would (though to be fair, I can't imagine what the OP thought it would do in the first place).

It uses the comma operator, which is completely legal. The comma operator evaluates both the left hand side and the right hand side and returns the right hand side. So the line is identical to:

Code:

---

nrb;
ggd=nra%nrb;

---

The "nrb;" line doesn't make much sense though.


To the OP: This wasn't a problem with not knowing the algorithm. You should read up on function calls, and recursive functions. Because the algorithm you tried seems to be the recursive version, but it doesn't look much like a function call at all :p.

hmm.. it's good that you pointed that out..
and it's true.. but I'm still at chapter 4 of my course.. but I'm learning more by browsing this forum than doing my exercises....