PRPALIN - Editorial

PROBLEM LINK:

Practice

Author: ADMIN

Editorialist: SUSHANT AGARWAL

DIFFICULTY:

SIMPLE

PREREQUISITES:

Basic looping,Conditional statements

PROBLEM:

You will be given an integer N, 1 ≤ N ≤ 1000000. You must find
the smallest integer M ≥ N such that M is a prime number and M is a
palindrome.

EXPLANATION:

Check every odd number after N (using a loop) for 2 properties

1)It should be prime 2) The number should be equal to its reverse.

Print the first number that satisfies these 2 properties and then break out of the loop when this number is encountered.

EDITORIALIST’S SOLUTION:

Editorialist’s solution can be found here.

1 Like

#include<stdio.h>
#include<math.h>
int check(int num)
{
int rev_num = 0;
while(num > 0)
{
rev_num = rev_num*10 + num%10;
num = num/10;
}
return rev_num;
}
int main()
{
int n,i;
scanf("%d",&n);
if(n==1)
{
printf(“2\n”);
}
else if(n==2)
printf(“3\n”);
else{
if(n%2==0)
n++;
else
n=n+2;
do{
int x=sqrt(n);
for(i=3;i<=x;i++)
{
if(n%i==0)
break;
}
if(n%i!=0)
{ int j=check(n);
if(j==n)
{ printf("%d\n",n);
break;
}
}
n=n+2;
}while(1);
}
return 0;
}
why this not work

The solution given in this editorial is wrong. For the input of 10010 it gives output 10201 but rather it should be 10301

answer is right…10201 is smaller than 10301

1 Like

why my solution is going for tle,…
http://www.codechef.com/viewsolution/6782096

10201 is divisible by 101
hence it is not a prime no
Hence the awnser for 10010 is 10301

10201 is divisible by 101
hence it is not a prime no
Hence the answer for 10010 is 10301

sir i have applied seive of atkins to found prime but still getting tle

have u submitted it or checking it in codechef IDE?

Serious issue - Editorialist’s solution is wrong as output for 10000 is 10201 which is 101^2.
This also means that the testcases are weak.

Nice job, but please format your code if you want someone to be able to understand it easily - use for example this - http://prettyprinter.de/index.php

…after N…

is not correct, M >= N right?

1 Like

Please ask questions in Discuss -> Forums -> Ask a Question.

Do not post questions like this as an answer.

Someone please check out this issue

What’s wrong with my code?

#include<stdio.h>
#include<math.h>
int main()
{
int n,i,j,t,count,rev;
scanf("%d",&n);
for(i=n+1;i<=1100000;i++)
{
t=i;
rev=0;
while(t!=0)
{
rev=rev*10+(t%10);
t=t/10;
}
if(rev==i)
{
count=0;
for(j=1;j<=rev;j++)
{
if(rev%j==0)
{
count++;
}
}
if(count==2)
{
printf("%d",rev);
break;
}
}
else
{
continue;
}
}
}

#include <bits/stdc++.h>

using namespace std;

bool isPalin(int i)
{
string num = to_string(i);
for(int i=0,j=num.length()-1;i<j;i++,j–){
if(num[i]!=num[j]){
//cout<<" false";
return false;

    }
}
return true;

}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int min;
cin>>min;
for(int i = 2 ; i<=10000000;++i)
{
bool flag = true;
for(int j = 2;j<=sqrt(i);++j )
{
if(i%j==0){
flag = false;
break;
}
}
if(flag && isPalin(i) && i>=min){
cout<<i;
break;
}
}

return 0;

}

// What’s wrong with the code, can anyone help me out!