If you calculate all numbers up to ~1.5M, then, unfortunately, your approach is not correct. You'd have to search for some algorithm to calculate Nth Fibonacci number without calculating all numbers below N. Even with memoization, "regular" approach will be probably too slow.

There are algorithms which calculate Nth Fibonacci number with fewer intermediate steps. Try researching a bit more, their descriptions are not very difficult to find.