gleeful bash scripting: contrived GCD function

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 
33
33
33
 5
77
1313
3131
3737
211211
241241
21612161
36073607
38033803
29061612906161

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.

1 comment

  1. 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.

Leave a comment

Your email address will not be published. Required fields are marked *