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