Почему такая относительная эффективность этих подпрограмм в системе Mathematica?

Я был удивлен разницей во времени, которую Даниэль Лихтблау указал на двумя способами, чтобы получить разницу между количеством простых множителей ( PrimeOmega ) и количеством различных простых множителей ( PrimeNu ) целого числа. , п. Поэтому я решил изучить это немного подробнее.

Функции g1 и g2 ниже представляют собой небольшие вариации , , которые использовал Даниэль, а также три других.Все они возвращают количество целых чисел без квадратов от 1 до n. Но различия довольно разительны. Может ли кто-нибудь объяснить причины различий. В частности, почему Sum в g5 обеспечивает такое преимущество в скорости?

g1[n_] := Count[PrimeOmega[Range[n]] - PrimeNu[Range[n]], 0]

g2[n_] := Count[With[{fax = FactorInteger[#]}, 
 Total[fax[[All, 2]]] - Length[fax]] & /@ Range[n], 0]

g3[n_] := Count[SquareFreeQ/@ Range[n], True]

(* g3[n_] := Count[SquareFreeQ[#] & /@ 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]}]  

Сравнение:

n = 2^20;
Timing[g1[n]]
Timing[g2[n]]
Timing[g3[n]]
Timing[g4[n]]
Timing[g5[n]]

Результаты:

{44.5867, 637461}
{11.4228, 637461}
{4.43416, 637461}
{1.00392, 637461}
{0.004478, 637461}

Редактировать:

Mysticial повысили возможность того, что последние подпрограммы пожинали плоды своего порядка - что могло происходить какое-то кеширование.

Итак, давайте запустим сравнение в обратном порядке:

n = 2^20;
Timing[g5[n]]
Timing[g4[n]]
Timing[g3[n]]
Timing[g2[n]]
Timing[g1[n]]

Результаты обратных сравнений:

{0.003755, 637461}
{0.978053, 637461}
{4.59551, 637461}
{11.2047, 637461}
{44.5979, 637461}

Вердикт: разумное предположение, но не подтвержденное данными.