Reducing Fractions in C

[Zexious]

I have a code here that takes in a numerator and a denominator value, and then outputs the result in a fraction form if needed.

#include <stdio.h>#include <stdlib.h>


int main(int argc, char *argv[])
{
  int a,b,ans,left;


  printf("Numerator\n");
  scanf("%d", &a);
  printf("Denominator\n");
  scanf("%d", &b);
     
  ans = a / b;
  left = a%b;
  
  if (left > 0){
           printf("\n%d %d/%d\n", ans, left, b);
}
  else{ 
        printf("\n%d\n", ans);


}
  system("PAUSE");	
  return 0;
}

It also needs to reduce the output. I don't know how to reduce my output and not sure how. Ex:

Numerator: 55
Denominator: 10

My ans: 5 5/10

Anyone know how to reduce the 5/10 in my program?

[javaeyes]

Read about the modulus operation:
Modulus Operator in C and C++ - Programming Tutorials - Cprogramming.com

[oogabooga]

You need to find the gcd (greatest common divisor) of the numerator and denominator, then divide them both by it. Euclid's algorithm is commonly used for finding the gcd. Google it.

[Zexious]

@ javaeyes

I know how the modulus operator works, that is why i used it in line 15 of my program for the numerator of the mixed fraction.

@ oogabooga

I did read Euclid's algorithm, but I'm just stumped on how it works. Yes I am not the smartest :/

Anyone else have any ideas?

[laserlight]

I did read Euclid's algorithm, but I'm just stumped on how it works.

What stumped you about the algorithm? Note that you only need to know how it works so that you can implement it.

[javaeyes]

OOps, right didnt see that. I think you may need to reduce the numerator and denominator to their prime factorization. 20 / 30 is a simple example.
20's prime factorization is 2^2 * 5^1 . 30's prime factorization is 2^1 * 3^1 * 5^1. when you start canceling terms (basically subtracting the exponents)
you're left with 2^1 / 3^1 or 2/3.
Now that I just read euclids alg, that is actually probably the way to go. This would work too though.

[oogabooga]

The only way to reduce a fraction to lowest terms is to divide top and bottom by their greatest common divisor (or cancel common factors, but that amounts to the same thing). Euclid's algorithm is the simplest way to find their gcd, so it's your best bet.

This is the pseudocode from the wikipedia article on Euclid's algorithm:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

Can you translate that into C?

[shruthi]

Implemented GCD and added it to your program,to reduce the fraction.

#include <stdio.h>
#include <stdlib.h>
int gcd(int,int);
#define TRUE 1
#define FALSE 0


int main(int argc, char *argv[])
{
  int a,b,ans,left,g,n,d;




  printf("Numerator\n");
  scanf("%d", &a);
  printf("Denominator\n");
  scanf("%d", &b);




  ans = a / b;
  left = a%b;
  g=gcd(left,b);


    if(left==0)
     printf("\n%d\n", ans);


   else if (g==1 && left > 0)
  {
           printf("\n%d %d/%d\n", ans, left, b);
  }
  else
  {
         left=left/g;
          b=b/g;
           printf("\n%d %d/%d\n", ans, left, b);
  }






  system("PAUSE");
  return 0;
}
int gcd(int n,int d)
{
    int r; //remainder


    while((n%d!=0) || (d<=0))


    {
        r=n%d;
        n=d;
        d=r;
    }
     if(n%d==0)
     {
     return d;
     }
     else
     return FALSE;
}