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