Quote:

Originally Posted byCOKEDUDEWow your code is so much simpler and easier to use . Thx for the code. I'm just stubborn about making up my own stuff sometimes.

Have fun coding!

Quote:

Originally Posted byCOKEDUDEWow your code is so much simpler and easier to use . Thx for the code. I'm just stubborn about making up my own stuff sometimes.

Have fun coding!

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(); }

But for() loop should be this way;

Code:

for(n=1;n%a != 0 || n%b != 0;n++); return n;

Code:

int gcd(int a,int b) { while((a=a%b)&&(b=b%a)); return a+b; }

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,

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

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

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; }

Therefore GCD(18,24) = last remainder = 6 //Euclid's Algorithm

Quote:

Originally Posted bykadrix_vskpThe correct code:

for( n = 1; n%a != 0 || n%b != 0; i++);

return n;

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; } }