#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 5-6 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.