Help For Tle (Answer is 100% correct)

general
1

#include<stdio.h>
#include<math.h>
main()
{
int n,i;
scanf("%d",&n);

while(1)
{

if(n%2!=0 && prime(n)==0 && reverse(n)==0)
{
printf("%d\n",n);
break;
}
else{n= n+1;}

}
return 0;

}

int reverse(int n)
{
int temp,rem;
int reve =0;
int flag =1;
temp = n;
while(temp!=0)
{
rem = temp % 10;
reve = reve*10 +rem;
temp = temp/10;
}
if(reve==n)
{
flag = 0;
}
return(flag);
}

int prime(int n)
{
int i;
int flag =0;

for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
flag = 1;
}
}
return(flag);

}

my solution is fine but i am getting “TIME LIMIT ERROR” so if some one could help me in optimising this code .
it just check whether number is a prime and is a palindrome or not using two function
http://www.codechef.com/problems/PRPALIN/ —> it’s a practice question

2

You have declared n as int but range of n is beyond int maybe because of that your are getting tle
try using long long int also change %d to %lld for long long int.
Your logic is correct

3

Hello @rgpt

There are many places where your code can be optimized for speed. The most effective ones are in your prime checking function. You should add break statement if n is divisible. Also when asking for help, always format your code correctly or provide a link for better readability.

int prime(int n) { 
int i,flag=0,lim=sqrt(n);      //sqrt calculated only once, not every time
    for(i=3;i<lim;i+=2){       // loop starts from 3 for speed up as we have already skipped even //numbers and increase by 2 in each step
        if(n%i==0) {
            flag=1;
            break;  // added break here
        }
    }
    return(flag);
}

Other places need to be modified too for faster execution.

See your code accepted with a lot of speed up modifications by me here.

4

@nitrek

No, long long int is not the solution here. The constraint in the problem is

1 ≤ N ≤ 1000000

which can very well fit in integer datatype.

5

The worst case complexity of your solution is O(N*sqrtN).
For the given problem it becomes 10^9 iterations.
But in 1s (time limit for the problem) your processor( or codechef’s which is even slower) can perform about 10^6 iterations resulting in almost 1000s for the worst case.

Solution :- Use sieve of eratosthenes.