"Vaishnav and Pizzas" challenge
Yes, the execution time amounts to O(n^3) because of the nested loops. A brute force approach cannot be healed; you need to change the algorithm.

A given denominator Q produces exactly phi(Q) rational numbers, so the problem boils down to calculating $$ \sum \phi (k) $$

There are many approaches for doing that. For the small numbers (according to constraints, less than 10000) I'd recommend a straightforward use of multiplicative property. A precomputed table of primes may also help.