TLE here but not on ideone

general
1

hello,i don’t understand why do i get tle for prime palindrome it is working fine on ideone have a look at solution—>link

2

Edited: Eliminate unnecessary function calls like for for any i which is even, you know that cannot be the answer. Use scanf, printf () for io. That may amend your TLE verdict. If you’re still getting TLE (reason in comments), usually, what people do in such questions is find all possible prime numbers which are palindromes using brute force(if the constraints which is possible in this problem) and then output the answer in much less time and computation. See my


[1] for that.


  [1]: http://www.codechef.com/status/PRPALIN,damn_me
1 Like
3

thanks for reply :slight_smile: but see in question it is written number greater or equal to the number.if i will change i=n to i=n+1 than many cases may get wrong as the original number will not get consider.If line 35 is wrong than how to improve .

4

Oh, I missed that point. Check for condition inside the loop that if i is even, then there’s no need to call the two functions as we know that cannot be a prime number.

5

thanks…one last thing i would like to know :slight_smile: that whats the time complexity of my code,i feel difficulty in finding time complexity of these type of code. :slight_smile: :slight_smile:

6

Try calculating this way: Your every value of i in for loop of main() you’ll have no_of_time_isprime + no_of_time_ispalindrome i.e. number of operations both the function performs which is sqrt(num)+(no_of_digits_num). These much operations will be there for every value of i, thus total is (100000-n)*(sqrt(i)+(no_of_digits_i)) . This is what will happen in worst case. And thus you can fairly assume that its tough for your code to pass the constraints.

1 Like
7

why 100000-n ??

8

Oh, i thought of writing something else, in place of (100000-n), it’ll be (p-n) where p is the smallest prime number which will be your answer. So in the first case you can see that n is 100000 and answer for this is 1003001 so the maximum number of iterations can be till (1003001-n) as we hope to find answers for all other values of n till this number.

1 Like