#include<stdio.h>
int main()
{
int n,i,j,count=0,temp,rem=0,rev=0;
scanf("%d",&n);
for(i=n;;i++)
{
for(j=1;j<=i;j++)
{
if(i%j==0)
count++;
}
temp=i;
while(i>n)
{
rem=i%10;
rev=rev*10+rem;
i=i/10;
}
if(count==2 && rev==temp)
{
break;
}
}
printf("%d",i);
return 0;
}
Use this algorithm:
First generate all primes till sqrt(1030000) (And try to use an efficient algorithm for this)
for(i=n;;i++)
{
temp=i;
Check if temp is palindrome<Br>
If (temp is palindrome)<Br>
{
check if i is prime
For checking i as prime divide with all primes till the sqrt(i)( no need to divide with all numbers less than the number itself )
}
If(i is prime and palin)<Br>
break;<BR>
}
print i;
This should work, if the prime generation method is good.
I originally solved this problem in Java
Now, I have also solved it in C, so that you can understand.
Here’s the link: CodeChef: Practical coding for everyone
Now,
I have divided the problem into functions,
Check out the first function void generate_primes(), observe it carefully and try to understand.

This function generates the primes till the sqrt(1030000)

It generates the primes by checking if a number is divisible by any prime number less than the square root of the number. It uses the generated primes side by side for performing this check.

Firstly, we store pr[0]=2, After this all primes are odd,
so no need to check for even. That’s why the for loop starts from 3 and has an increment of 2.

Now lets execute this code, step by step:
i=3, pr[0] * pr[0]< = i is false, loop not executed, f==0
So pr[1]=3 is assigned
i=5, pr[0]*pr[0]<=i is true, loop executed, but condition i%p[j] (i%2) is false
pr[1] * pr[1]<=i is false, f still 0.
So, pr[2]=5 is assigned.
<Br>
Similarily execute it for 56 more values manually.
Now you have the primes in the array pr[], so to check if a number is prime, check for divisibility by the primes less than the square root of the number. No need to check all the numbers till the number or till sqrt(number).<Br><Br><BR>
**Do not copy the code, try to understand it and then code it yourself.**
Happy Coding<Br>
Cheers.<BR>
i am still not getting the right answer…
could you please give me an efficient algorithm for checking prime…??
I have posted an efficient method for generating primes!
Check the answer below.
i was wondering if you could tell me how did you declare the array size of 1000005 for the primes. Was it a guess or some logic behind this.
Please Reply ASAP.