Why my solution is getting time limit exceed in test case 2?

Question

Problem Link :
https://acm.timus.ru/problem.aspx?space=1&num=1086

Solution of mine:
https://code.sololearn.com/cQ8wVh9sqkwa/?ref=app

I know It's happening because of time complexity O(n^3). Still if by changing this code slightly makes the code get accepted then let me know please. Thank you.

Answer 1

for (j = 2; j <= i/2; j++){
if(i%j == 0){
count++;
break;
}
}
this loop can be optimised as :

for (j = 2; j <= sqrt(i); j++){
if(i%j == 0){
count++;
break;
}
}

if this too doesn't work , try sieve of eratosthenes.

Answer 2

Caching the primes should be a big improvement
If you initialize the cache with [2], i can start at 3 and increase by 2