Why is doing a computation inside Select slower than a precomputation?

Question

I am trying to generate primitive Pythogorean triples using Euclid's parametrization. I basically want a list of pairs with ordered pairs $(m,n)$ such that $m$ and $n$ are coprime.

My first approach was

AbsoluteTiming[
 list1 = Flatten[Table[{m, n}, {m, 1, 20000, 2}, {n, 2, 20000, 2}], 1];
 list2 = Select[list1, (GCD[#[[1]], #[[2]]] == 1) &];]

(*{223.175, Null}*)

in which I first produce a list of pairs where $m$ is always odd and $n$ is always even. Then I use Select to select the pairs where both coordinates are coprime. I quit and restarted a local kernel with a simple computation like 2+2 to make sure there are no effects due to caching, garbage cleanup, or something like that. I then timed the whole thing and got 223 seconds.

My second approach was

AbsoluteTiming[
 list1 = Flatten[
   Table[{m, n, GCD[m, n]}, {m, 1, 20000, 2}, {n, 2, 20000, 2}], 1];
 list2 = Select[list1, #[[3]] == 1 &];]

(*{161.464, Null}*)

in which I compute a third column inside the Table which is the GCD of $m$ and $n$. Then I used Select to simply pick the lists where the third coordinate is one. Restarting the kernel as before and timing it gives me only 161 seconds, which is almost 40% faster.

Why is the first method slower? I don't care about the memory usage. Obviously storing the third column will take more memory.

My thoughts,

• I would expect both of them to take roughly the same amount of time. If anything, I would expect the second approach to be slower. We are flattening an array with more elements.
• They are both vectorized approaches.
• The kernel is doing all of the work (instead of the front-end) in both cases.
• The number of GDC operations is the same in both cases.
• The number of comparisons is the same in both cases.
• In the first case, Select is scanning row-by-row, computing the GCD, and comparing it to one.
• In the second case, Table is computing the GCD row-by-row and Select is only scanning the third column and comparing it to one.

Which of these, if any, is wrong? The only thing I can think of is that in the first approach Select is scanning both the first and the second column. In the second approach Select is only concerned with the third column ignoring the first two columns completely. Is this true?

What is going on here? What are the lesson to be learned here, in the context of writing fast MMA code?