10235  Simply Emirp
Moderator: Board moderators
TLE.......
[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void prima(long int a);
void main()
{ long int N;
while(scanf("%li",&N)!=EOF)
{ prima(N);
}
}
void prima(long int a)
{ long int i,t,p,d,ctr=0;
char c[8]={NULL};
for(i=1;i<=a;i++)
{ if(a%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is not prime.\n",a);
}
else
{ sprintf(c,"%li",a);
p=strlen(c);
for(i=0;i<(p/2);i++)
{ t=c;
c=c[pi1];
c[pi1]=t;
}
sscanf(c,"%li",&d);
ctr=0;
for(i=1;i<=d;i++)
{ if(d%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is prime.\n",a);
}
else printf("%li is emirp.\n",a);
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void prima(long int a);
void main()
{ long int N;
while(scanf("%li",&N)!=EOF)
{ prima(N);
}
}
void prima(long int a)
{ long int i,t,p,d,ctr=0;
char c[8]={NULL};
for(i=1;i<=a;i++)
{ if(a%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is not prime.\n",a);
}
else
{ sprintf(c,"%li",a);
p=strlen(c);
for(i=0;i<(p/2);i++)
{ t=c;
c=c[pi1];
c[pi1]=t;
}
sscanf(c,"%li",&d);
ctr=0;
for(i=1;i<=d;i++)
{ if(d%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is prime.\n",a);
}
else printf("%li is emirp.\n",a);
}
}
[/c]
can anyone tell me why my code is TLE?
I test it on my C compiler and it runs quite fast.....
[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void prima(long int a);
void main()
{ long int N;
while(scanf("%li",&N)!=EOF)
{ prima(N);
}
}
void prima(long int a)
{ long int i,t,p,d,ctr=0;
char c[8]={NULL};
for(i=1;i<=a;i++)
{ if(a%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is not prime.\n",a);
}
else
{ sprintf(c,"%li",a);
p=strlen(c);
for(i=0;i<(p/2);i++)
{ t=c;
c=c[pi1];
c[pi1]=t;
}
sscanf(c,"%li",&d);
ctr=0;
for(i=1;i<=d;i++)
{ if(d%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is prime.\n",a);
}
else printf("%li is emirp.\n",a);
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void prima(long int a);
void main()
{ long int N;
while(scanf("%li",&N)!=EOF)
{ prima(N);
}
}
void prima(long int a)
{ long int i,t,p,d,ctr=0;
char c[8]={NULL};
for(i=1;i<=a;i++)
{ if(a%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is not prime.\n",a);
}
else
{ sprintf(c,"%li",a);
p=strlen(c);
for(i=0;i<(p/2);i++)
{ t=c;
c=c[pi1];
c[pi1]=t;
}
sscanf(c,"%li",&d);
ctr=0;
for(i=1;i<=d;i++)
{ if(d%i==0) ctr++;
}
if(ctr!=2)
{ printf("%li is prime.\n",a);
}
else printf("%li is emirp.\n",a);
}
}
[/c]
can anyone tell me why my code is TLE?
I test it on my C compiler and it runs quite fast.....
hi r.z.,
i am pretty positive you are getting TLE because of the way you check primality.... in most problems where primes are involved it's worth to pregenerate the primes in an array, and in this particular problem just binsearch that array to see if the number you have is there or not... if you look at your prime method, you realize that you do a lot of redundant checking, ie: you check if a is divisible w/ 2, 4, 6....
so just pregenerate all the primes, and I am sure you won't get tle
g'luck,
zsepi
i am pretty positive you are getting TLE because of the way you check primality.... in most problems where primes are involved it's worth to pregenerate the primes in an array, and in this particular problem just binsearch that array to see if the number you have is there or not... if you look at your prime method, you realize that you do a lot of redundant checking, ie: you check if a is divisible w/ 2, 4, 6....
so just pregenerate all the primes, and I am sure you won't get tle
g'luck,
zsepi
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
hmmmm
I also get WA.....
[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
void cek(long int a);
int prima(long int in);
void main()
{ long int N;
while(scanf("%li",&N)!=EOF)
{ cek(N);
}
}
void cek(long int a)
{ long int i,t,p,d;
char c[8]={NULL};
if(!prima(a))
{ printf("%li is not prime.\n",a);
}
else
{ sprintf(c,"%li",a);
p=strlen(c);
for(i=0;i<(p/2);i++)
{ t=c;
c=c[pi1];
c[pi1]=t;
}
sscanf(c,"%li",&d);
if(!prima(d))
{ printf("%li is prime.\n",a);
}
else printf("%li is emirp.\n",a);
}
}
int prima(long int in)
{ long int i;
if(in<2) return 0;
for(i=2;i<=sqrt(in);i++)
{ if(in%i==0) return 0;
}
return 1;
}
[/c]
the output seems ok
I also get WA.....
[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
void cek(long int a);
int prima(long int in);
void main()
{ long int N;
while(scanf("%li",&N)!=EOF)
{ cek(N);
}
}
void cek(long int a)
{ long int i,t,p,d;
char c[8]={NULL};
if(!prima(a))
{ printf("%li is not prime.\n",a);
}
else
{ sprintf(c,"%li",a);
p=strlen(c);
for(i=0;i<(p/2);i++)
{ t=c;
c=c[pi1];
c[pi1]=t;
}
sscanf(c,"%li",&d);
if(!prima(d))
{ printf("%li is prime.\n",a);
}
else printf("%li is emirp.\n",a);
}
}
int prima(long int in)
{ long int i;
if(in<2) return 0;
for(i=2;i<=sqrt(in);i++)
{ if(in%i==0) return 0;
}
return 1;
}
[/c]
the output seems ok

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
be careful with numbers which are prime and it's reverse is prime too ...
It looks like your method fails in such case....
Best regards
DM
It looks like your method fails in such case....
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I forgot about one thing:
think about numbers which have reverse the same as start number
Best regards
DM
think about numbers which have reverse the same as start number
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
10235 wa ,,all the time ,, plizzzzzzzzzzzzzzzz help
i am having wa all the time . i cant find any prob with my code . i tried in different methods , but getting wa all the time . here is my latest try .plizzzzzzzzzzzzzzzzzzzzzzzzz help me
here is my code :
waiting for u r help
Bye
Riyad
here is my code :
Code: Select all
#include<stdio.h>
#include<math.h>
long int reverse_num(long int input){
long int output=0;
while(1){
if(input<=0){
break;
}
output=10*output+(input%10);
input/=10;
}
return output;
}
int check(long int x){
register long int i;
for(i=2;i<sqrt(x);i++){
if((x%i)==0){
return 0;
}
else
continue;
}
return 1;
}
int main(){
long int num,rnum;
register int pflag,eflag;
while(scanf("%ld",&num)==1){
pflag=check(num);
rnum=reverse_num(num);
if(rnum!=1){
eflag=check(rnum);
}
else{
eflag=0;
}
if(pflag==0){
printf("%ld is not prime.\n",num);
}
else if(pflag==1 && eflag==0){
printf("%ld is prime.\n",num);
}
else if(pflag==1 && eflag==1){
printf("%ld is emirp.\n",num);
}
}
return 0;
}
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

 Experienced poster
 Posts: 136
 Joined: Tue Apr 01, 2003 6:59 am
 Location: Jakarta, Indonesia
i got it ac , at last
sorry for my being stupid and over look a term "DIFFERENT PRIME"in the problem. that means when we reverse a number if it is the same number and holds the property of the "emirp" , it wont count . lets take an example 101 , which is a prime number , if we reverse 101 it stand 101 which is also a prime , so it should be a "emirp" , but it is not counted as a "emirp" coz
An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed.
An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed.
thanx any way for u r suggestion , u were right about "1" . but i guess it is not in the judges test input . for "7" the output is only prime(not emirp)
BYe
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
i got it ac , at last
sorry for my being stupid and over look a term "DIFFERENT PRIME"in the problem. that means when we reverse a number if it is the same number and holds the property of the "emirp" , it wont count . lets take an example 101 , which is a prime number , if we reverse 101 it stand 101 which is also a prime , so it should be a "emirp" , but it is not counted as a "emirp" coz
BYe
Riyad
thanx any way for u r suggestion , u were right about "1" . but i guess it is not in the judges test input . for "7" the output is only prime(not emirp)An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed.
BYe
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

 Experienced poster
 Posts: 136
 Joined: Tue Apr 01, 2003 6:59 am
 Location: Jakarta, Indonesia

 New poster
 Posts: 30
 Joined: Wed Oct 23, 2002 6:53 am