title: Why the relative efficiency of these routines in Mathematica?
body: <p>I was surprised by  a timing difference that Daniel Lichtblau <a href="https://stackoverflow.com/questions/7769613/mathematicas-puzzling-interpretation-of-2-rangen/7770886#7770886">pointed out</a> in two ways to get at the differences between the number of prime factors (<code>PrimeOmega</code>) and the number of distinct prime factors (<code>PrimeNu</code>) of an integer, n. So I decided to look into it a bit further.</p>
  
  <p>The functions <code>g1</code> and <code>g2</code> below are slight variations of the <a href="https://stackoverflow.com/questions/7769613/mathematicas-puzzling-interpretation-of-2-rangen/7770886#7770886">ones</a> Daniel used as well as three others. They all return the number of square-free integers from 1 through n.  But the differences are fairly dramatic.  Can anyone explain the reasons behind the differences. In particular, why does the <code>Sum</code> in <code>g5</code> provide such a speed advantage?</p>
  
  <pre><code>g1[n_] := Count[PrimeOmega[Range[n]] - PrimeNu[Range[n]], 0]
  
  g2[n_] := Count[With[{fax = FactorInteger[#]}, 
   Total[fax[[All, 2]]] - Length[fax]] &amp; /@ Range[n], 0]
  
  g3[n_] := Count[SquareFreeQ/@ Range[n], True]
  
  (* g3[n_] := Count[SquareFreeQ[#] &amp; /@ Range[n], True] Mr.Wizard's suggestion
     incorporated above. Better written but no significant increase in speed. *) 
  
  g4[n_] := n - Count[MoebiusMu[Range[n]], 0]
  
  g5[n_] := Sum[MoebiusMu[d]*Floor[(n - 1)/d^2], {d, 1, Sqrt[n - 1]}]  
  </code></pre>
  
  <p>The comparison:</p>
  
  <pre><code>n = 2^20;
  Timing[g1[n]]
  Timing[g2[n]]
  Timing[g3[n]]
  Timing[g4[n]]
  Timing[g5[n]]
  </code></pre>
  
  <p>The results:</p>
  
  <pre><code>{44.5867, 637461}
  {11.4228, 637461}
  {4.43416, 637461}
  {1.00392, 637461}
  {0.004478, 637461}
  </code></pre>
  
  <hr>
  
  <p><strong>Edit:</strong></p>
  
  <p>Mysticial raised the possibility that the latter routines were reaping the benefits of their order--that some caching may have been going on.</p>
  
  <p>So let's run the comparison in the reverse order:</p>
  
  <pre><code>n = 2^20;
  Timing[g5[n]]
  Timing[g4[n]]
  Timing[g3[n]]
  Timing[g2[n]]
  Timing[g1[n]]
  </code></pre>
  
  <p>Results of reversed comparisons:</p>
  
  <pre><code>{0.003755, 637461}
  {0.978053, 637461}
  {4.59551, 637461}
  {11.2047, 637461}
  {44.5979, 637461}
  </code></pre>
  
  <p>Verdict: A reasonable guess, but not supported by the data.</p>