Let ~F = \max(f_1, f_2, \dots, f_N)~.

For ~10\%~ of points, we can iterate through each slice of cake, and then all integers from ~2~ to ~f_i-1~, to check if any of them are a factor of ~f_i~.

Time Complexity: ~\mathcal O(N F)~

For an additional ~10\%~ of points, we can process all the numbers from ~2~ to ~F~, and record if they are prime or not in a boolean array, and then check if each ~f_i~ is prime or not.

Time Complexity: ~\mathcal O(N + F^2)~

For the final ~80\%~ of points, make the observation that if ~a_i~ is a factor of ~f_i~ and ~a_i \le \sqrt{f_i}~, then ~\dfrac{f_i}{a_i} \ge \sqrt{f_i}~. Namely, we only have to check for factors in the range ~[2, \sqrt{f_i}]~.

Alternatively, one could use a prime sieve, such as the sieve of Eratosthenes.

Time Complexity: ~\mathcal O(N + F \sqrt F)~ or ~\mathcal O(N \sqrt F)~, or ~\mathcal O(N + F \log \log F)~ with the sieve of Eratosthenes.