My solution was expected to get TLE

In last lunchtime, my solution for problem Cute Chef Gift was expected to get TLE on subtask 3. Worst case complexity for each test case is O(n * num_of_primes_less_than(1e5)). But it was accepted.

1 Like

If I’m not wrong your solution in not O (n * number_of primes_less_than…), but O(n * m) where m is the maximum number of distinct primes in the factorization of a number less than 1E5.

m = 6 \rightarrow 2 * 3 * 5 * 7 * 11 * 13

There’s no number less than 1E5 that can be divided by more than 6 distinct primes

[EDIT] didn’t say anything, I checked your code and now I see you loop for all primes inside the last for loop, so you are right

1 Like