Greatest Common Divider

This is a discussion on Greatest Common Divider within the C Programming forums, part of the General Programming Boards category; Hi I'm trying to calculate the greatest common divider. But I guess there's something wrong with my algorythm to calculate ...

  1. #1
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49

    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;
    }
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

  2. #2
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49
    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
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

  3. #3
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Code:
    ggd=(nrb,nra%nrb);
    is not syntactically correct.

  4. #4
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49
    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
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

  5. #5
    msh
    msh is offline
    Novice
    Join Date
    Jul 2009
    Posts
    568
    Go wiki "Euclidean algorithm".

  6. #6
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49

    Question

    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;
    }
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

  7. #7
    msh
    msh is offline
    Novice
    Join Date
    Jul 2009
    Posts
    568
    And what stops you from plugging either of those into calculate()?

  8. #8
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49
    tried that. gives all sorts of errors... :/ like: extraneous return value, unrecognized statement. expected this but found that.
    and so on....
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

  9. #9
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49
    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;			
    }
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by nonoob View Post
    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 .

  11. #11
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49
    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....
    Last edited by Bennie98; 11-15-2010 at 08:50 AM.
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Greatest Common Divisor.....
    By muran_pling in forum C++ Programming
    Replies: 10
    Last Post: 12-18-2006, 04:02 AM
  2. Greatest Common Divisor problem
    By fenixataris182 in forum C++ Programming
    Replies: 8
    Last Post: 07-12-2005, 07:55 PM
  3. Greatest common divisor
    By wiz23 in forum C++ Programming
    Replies: 5
    Last Post: 04-13-2005, 04:50 PM
  4. Greatest common divisor with int and double
    By wiz23 in forum C++ Programming
    Replies: 3
    Last Post: 04-12-2005, 04:38 PM
  5. Greatest Common Factor problem
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 10-08-2001, 03:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21