Used an std::map, time is now around .526s
Included both optimizations and used shorts
Used an int array as a cache for values <=1 million, kept std::map for greater values though
Made the ref getter function inline