phi(n) and GCD(m,n)
Attempts are often made to graphically display the distribution of primes. Before one tries such attempts, it is educating to look first at the graph of Euler's Totient function phi(n) versus n.http://en.wikipedia.org/wiki/Euler%27s_totient_function
The totient function doesn't only show the distribution of primes, but also the distribution of all the composites as a density. In the graph of phi(n) vs n, the primes are seated at the top, belonging to the line x-1, since phi(p)=p-1 for primes.
Trend lines with increased density appear on the graph. They are the densities of composites of specific forms. For example, the line x/2 hosts composites of the form 2^n. The lines x/3 and 2x/3 host composites divisble by 3, etc. Highly composite numbers tend to congregate towards the bottom and composites with large prime factors tend to congregate near the top (below the x-1 line).
Now look at the graph of execution speed performance of the GCD(m,n) algorithm. In this graph, black denotes highest speeds (fast completion) and white slowest, for all positive m,n with 1<=m,n<=200.http://en.wikipedia.org/wiki/Euclidean_algorithm
Finally check the graphs of the totient and GCD performance combined in Photoshop. You can obviously ignore the symmetric part above the line x, since GCD(m,n)=GCD(n,m)
Can you express the evident connection as a theorem? :-)
[On this post the combined image shows first. The graphs of phi(n) and that of the GCD performance are shown separately in images 2 and 3]