I used trial division and it was too slow, but then i looked for other factors in my code to improve the execution time, and was able to greatly reduce the excecution time. As a somewhat spoiler free hint, i thnk that memoization was a big factor for making it, mine in particular, faster.

I have the same issue. But how to optimize the code? I've tryied, but can not pass the test.

Do this n times!

It's there ^

No, (21-21)+(21-20)+...