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.

24th Feb 2021, 7:45 PM
Samia Haque
Samia Haque - avatar
2 odpowiedzi
+ 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.
25th Feb 2021, 1:39 AM
Hima
Hima - avatar
+ 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
24th Feb 2021, 7:59 PM
Benjamin Jürgens
Benjamin Jürgens - avatar