Prime Palindromes wrong answer

general
, ,
1

#include
#include
using namespace std;
enum Boolean{FALSE,TRUE};
Boolean ispal(int a)
{
int num=a;
int digit=0,rev=0;
while(a>0)
{
digit=a%10;
rev=rev*10+digit;
a=a/10;
}
if(num==rev)
return TRUE;
else
return FALSE;
}
Boolean isprime(int n)
{
int flag=0;
for(int i=1;i<=n/2;i++)
{
if((n%i)==0)
flag++;
}
if(flag>1)
return FALSE;
else
return TRUE;
}
int main()
{
int input, output;
cin>>input;
for(long int i=input+1;i<10000000;i++)
{
if(isprime(i))
{
if(ispal(i))
{
cout<<i;
exit(0);
}
else
continue;
}
continue;
}
return 0;
}

This is the code that i submitted, and for 31 i am getting 101. but upon submission, i’m told that the answer is wrong, could someone please point out the error in the code?

2

It doesn’t return result for 1000000 in 5s on IdeOne (http://ideone.com/mSLgOg ), can you provide your result here?

3

I’m sorry betlista, this is going to sound rather dumb, but what output would you like me to include?

4

The one, that your code produces - result for that input…

5

gcc gives no output at all, same as what you mentioned in your answer. it works till 10000, but then, it just hangs.

6

It’s probably because you check for prime is slow, first switch ispal and isprime checks… Your for loop is incorrect too, for input 2 you return 3, but correct is 2, isn’t it?

7

swapping the function calls does the trick, it works now, although it exceeds the time limit, to make it more feasible, any hint?

8

As I wrote above, your isprime function is slow - it’s running in O(n/2) time, even for 1.000.000 your loop is executed 500.000 times…

Try to find out (do some paper work) if you really need to loop up to n/2 :wink: