Project Euler 503（3） - inamori’s diary

いろいろ工夫することによって高速化を図った。F(10¹²)まで計算したら、O(N^1/2)っぽくなった。普通の解法ならO(N)である。

F(10^6)  :  0.031sec
F(10^7)  :  0.090sec
F(10^8)  :  0.146sec
F(10^9)  :  0.296sec
F(10^10) :  1.893sec
F(10^11) :  4.472sec
F(10^12) : 12.769sec

また、計算量を減らすことにより精度が上がった。F(10⁶)で誤差4e-14程度、F(10⁹)で5e-12程度になった。