0

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

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.

2 Answers

+ 2

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.

+ 1

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