Greatest Common Denominator — Euclidian algorithm and a crappy count-all-the-factors one

gcd.c

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

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

int* fac(int n) {
  int max = (int) sqrt(n);
  int* factors = malloc(sizeof(int) * (2*max+1));
  int fi = 0;

  for (int i = 1; i <= n; i++) {
    if ((n % i) == 0) {
      factors[fi++] = i;
      factors[fi++] = n / i;
    }
  }

  // stop code
  factors[fi++] = -1;

  return factors;
}

int gcd_pfac(int a, int b) {
  int* fa = fac(a);
  int* fb = fac(b);

  int highest = 0;

  int i = 0;
  while (fa[i++] != -1) {
    int j = 0;
    while (fb[j++] != -1) {
      if ((fa[i] == fb[j]) && (fa[i] > highest)) {
        highest = fa[i];
      }
    }
  }

  return highest;
}

int main(int argc, char** argv) {
  if (argc < 3 || (argv[1][1] != 'p' && argv[1][1] != 'e')) {
    printf("Usage: %s [-p|-e] num_a num_b\n", argv[0]);
    exit(1);
  }

  int use_pfac = (argv[1][1] == 'p');
  int use_euc  = (argv[1][1] == 'e');

  int a = atoi(argv[2]);
  int b = atoi(argv[3]);

  if (use_euc) {
    printf("gcd(%d, %d) = %d\n", a, b, gcd_euc(a,b));
  } else if (use_pfac) {
    printf("gcd(%d, %d) = %d\n", a, b, gcd_pfac(a,b));
  }

  return 0;
}