The greatest common divisor (gcd) of two natural numbers is the largest number that evenly divides both. For instance *gcd(8, 12)* is 4. There are many clever and efficient ways to calculate the gcd of two numbers on a Linux machine. The method presented here is not among them.

#!/bin/bash

gcd(){ comm -12 --nocheck-order <(factor $1|sed 's/^[^ ]*/1/;s/ /\n/g') <(factor $2|sed 's/^[^ ]*/1/;s/ /\n/g')|tr '\n' \*|sed 's/.$/\n/'|bc;}

gcd $1 $2

(Contrived) example:

gcd.sh 24691357802469135780246913578 61728394506172839450617283945

12345678901234567890123456789

Which breaks down as:

prime factors of 24691357802469135780246913578 |
prime factors of 61728394506172839450617283945 |

2 | |

3 | 3 |

3 | 3 |

3 | 3 |

5 | |

7 | 7 |

13 | 13 |

31 | 31 |

37 | 37 |

211 | 211 |

241 | 241 |

2161 | 2161 |

3607 | 3607 |

3803 | 3803 |

2906161 | 2906161 |

Multiply the factors common to both:

3 × 3 × 3 × 7 × 13 × 31 × 37 × 211 × 241 × 2161 × 3607 × 3803 × 2906161 = 12345678901234567890123456789

I’m sure someone else has used the output of factor and comm in this way before. The hard part was getting coprime numbers to output 1.

## One reply on “gleeful bash scripting: contrived GCD function”

This doesn’t quite work: try

gcd 5652 8478

and it returns 18. Both 5652 & 8478 have 157 as a factor, so something’s wrong here.