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
grb47
2
#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
lincoln
3
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
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 - prettyprinter.de
…after N…
is not correct, M >= N right?
1 Like
arun_as
12
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!
It shows wrong answer in few test cases,… Can anyone help me to fix this
#include<iostream>`
using namespace std;
bool palindrome(long int n){
long int r,rev=0,c;
c=n;
while(n!=0){
r=n%10;
rev=rev*10+r;
n=n/10;
}
if(c==rev)
return true;
return false;
}
int main(){
long int n;
cin>>n;
if(n%2==0)
n++;
if(n==1)
n=3;
for(long int i=n;i<=1000000;i+=2){
int g=1;
for(long int j=3;j<=(i+1)/2;j+=2){
if(i%j==0){
g=0;
}
}
if(g==1 && palindrome(i)){
cout<<i;
break;
}
}
return 0;
}