After reading a very interesting article about Mobius function , I stumbled into one of the proposed problems, GCDEX2 . The problem is, all the proposed algorithms need O(N) memory, precalculation (to answer queries in time ), which is too much for the proposed constraint. Ideas? Thanks in advance.