Finding LCM & GCD in C

Discussion in 'C' started by pradeep, Oct 5, 2005.

  1. Zaiber

    Zaiber New Member

    Joined:
    Dec 16, 2009
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    It's no problem at all. I actually used one of the previous posters' code and fixed it out to make mine, all it needed was a little push. At first I thought my code wouldn't work both ways and made one similar to yours too, but it ended up working out so I kept and just posted it for future reference for anyone else. I am done with this class (finished with about 99.4%) so I might not be posting for a long time until I take another programming class.

    Have fun coding!
     
  2. COKEDUDE

    COKEDUDE New Member

    Joined:
    Feb 17, 2010
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Here's another way to do this depending on what exactly you are looking for. I can't post the link for some reason which is really annoying :(.

    Code:
    void main()
      {
          int n1,n2;
          clrscr();
          printf("\nEnter two numbers:");
          scanf("%d %d",&n1,&n2);
          while(n1!=n2)
          {
               if(n1>=n2-1)
                   n1=n1-n2;
               else
                   n2=n2-n1;
          }
          printf("\nGCD=%d",n1);
          getch();
      }
       
       
      Logic of HCF or GCD of any two numbers:
       
      In HCF we try to find any largest number which can divide both the number.
      For example:  HCF or GCD of 20 and 30 
      Both number 20 and 30 are divisible by 1, 2,5,10.
      HCF=max (1, 2, 3, 4, 10) =10
      Logic for writing program:
       
      It is clear that any number is not divisible by more than that number.
      In case of more than one number s, a possible maximum number which can divide all of the number s must be minimum of all of that numbers.
      For example:  10, 20, and 30
        Min (10, 20, 30) =10 can divide all there numbers.  
      So we will take one for loop which will start form min of the numbers and will stop the loop when it became one, since all numbers are divisible by one.  
      Inside for loop we will write one if conditions which will check divisibility of both the numbers.
       
      Program:
      void main(){
          int x,y,m,i;
          clrscr();
          printf("Insert any two number:  ");
          scanf("%d%d",&x,&y);
          m=x
          for(i=m;i>=1;i--){
               if(x%i==0&&y%i==0){
                   printf("\nHCF of two number is : %d",i) ;
                   break;
               }
          }
          getch();
      }
     
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    You can't post links cos you're new. It's a measure designed to stop spammers creating accounts and spamming us with links. This restriction is lifted after you've posted a few times and given us chance to see you're someone we want around.
     
  4. ysahn

    ysahn New Member

    Joined:
    Feb 25, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Good code sample.
    But for() loop should be this way;

    Code:
      for(n=1;n%a != 0 || n%b != 0;n++);
      return n;
    
     
  5. tango2

    tango2 New Member

    Joined:
    Mar 9, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    For finding the GCD of two positive integers, you can simply write:

    Code:
    int gcd(int a,int b) {
      while((a=a%b)&&(b=b%a));
      return a+b;
    }
    
     
  6. azeemigi

    azeemigi New Member

    Joined:
    Apr 3, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    OMG!!! You guys are got to be kidding right??? I just went through replies and 99% of them don’t make any sense. I just created the account to reply specifically to this post. COKEDUDE your last reply to this post is nonsense because it doesn't calculate the LCM. But however the answer is a CM.

    For example let's take number 18 and 24 and you want to find GCD(24,18).
    There are 2 methods we can use to find GCD. Those are,

    1) Prime Factorization
    According to the Prime Factorization you factorize the each number and find the "overlap" of the two expressions like following.

    18 = 2*3*3
    24 = 2*2*2*3

    Therefore the overlap value is 2*3
    Therefore GCD(18,24) = 2*3 = 6

    2) Euclid's Algorithm
    This is much more efficient method. Divide 24 by 18 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a quotient of 2 and a remainder of 0. Then divide 6 by 0 to get a remainder of 6, which means that 6 is the GCD.

    Therefore GCD(18,24) = 2*3 = 6

    Bellow is a code I wrote which will illustrate the GCD in both methods.

    Code:
    #include <stdio.h>
    #include <conio.h>
    
    int PrimeFactorization(int num1, int num2);
    int Euclid(int num1, int num2);
    
    void main(){
    
    	int num1 = 0, num2 = 0, primeFactorization = 0, euclid=0;
    
    	printf("\nEnter the 1st Integer: ");
    	scanf("%d", &num1);
    
    	printf("Enter the 2nd Integer: ");
    	scanf("%d", &num2);
    	primeFactorization = PrimeFactorization(num1, num2);
    	printf("\n\n\tThe GCD of %d and %d is (Prime Factorization): %d",num1,num2,primeFactorization);
    
    	euclid = Euclid(num1, num2);
    	printf("\n\n\tThe GCD of %d and %d is (Euclid's Algorithm): %d",num1,num2,euclid);
    }
    
    int PrimeFactorization(int num1, int num2){
    
    	int temp =1, i = 2,min = 0;
    
    	if (num1>num2)
    		min = num2;
    	else
    		min = num1;
    
    	while(i<min)
    	{
    		if((num1%i == 0) && (num2%i == 0))
    		{
    			num1 /= i;
    			num2 /= i;
    			temp *= i;
    		}
    		else
    			i++;
    	}
    	return temp;
    }
    
    int Euclid(int num1, int num2){
    
    	int temp =1, i = 2,min = 0,max = 0,remainder = 0;
    
    	if (num1>num2){
    		min = num2;
    		max = num1;
    	}
    	else{
    		min = num1;
    		max = num2;
    	}
    
    	while(min >= remainder){
    
    		remainder = max % min;
    		//printf("\n\tmin: %d\tmax: %d\t remainder: %d\t\n",min,max,remainder);
    
    		if (remainder == 0){
    			break;
    		}
    		else{
    			max = min;
    			min = remainder;
    		}
    	}
    
    	return min;
    }
    
     
  7. azeemigi

    azeemigi New Member

    Joined:
    Apr 3, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Therefore GCD(18,24) = last remainder = 6 //Euclid's Algorithm
     
  8. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Why 12? Where did this number come from?
     
    Last edited: Apr 4, 2010
  9. kadrix_vskp

    kadrix_vskp New Member

    Joined:
    Sep 23, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    The correct code:

    for( n = 1; n%a != 0 || n%b != 0; i++);
    return n;
    :)
     
  10. kadrix_vskp

    kadrix_vskp New Member

    Joined:
    Sep 23, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0

    Infact to compute the LCM of multple numbers say a, b, c, d quickly is:

    Code:
    int LCM(int a, int b, int c, int d)
    {
          int max = a;
          if(max < b)
                max = b;
          if(max < c)
                max = c;
          if(max < d)
                max = d;
    
          int lcm = max;
          while(1)
          {
                if(lcm%a == 0 && lcm%b == 0 && lcm%c == 0 && lcm%d == 0)
                      return lcm;
                lcm += max;
          }
    }
     
    Last edited by a moderator: Sep 23, 2010
  11. Ram Singh

    Ram Singh New Member

    Joined:
    Sep 27, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Study
    Location:
    Rewari
    Hi,
    I'm Ram Singh
    Please Help me create a programme Assending order any Five Nuber Through Array
     
  12. SaadBinSaulat

    SaadBinSaulat New Member

    Joined:
    Feb 15, 2011
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Re: Finding LCM & GCD in C++

    To get full source code for making a program for lcm and gcd calculation in c++, visit this cool link:
    bitsbyta.blogspot
     
  13. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Re: Finding LCM & GCD in C++

    There is no such program at that site.
     
  14. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
  15. sahar_2010

    sahar_2010 New Member

    Joined:
    Dec 29, 2010
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    no job,just studyning
    Location:
    Iran
    thanks so much:)
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice