10235 - Simply Emirp

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

Post by lendlice » Fri May 30, 2003 4:46 am

thanks
i got ac
:D

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. » Wed Jun 18, 2003 10:50 am

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[p-i-1];
c[p-i-1]=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[p-i-1];
c[p-i-1]=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.....

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. » Wed Jun 18, 2003 1:53 pm

ups I pasted it twice.....

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

Post by zsepi » Wed Jun 18, 2003 11:39 pm

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
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.

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. » Fri Jul 04, 2003 3:16 pm

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[p-i-1];
c[p-i-1]=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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Jul 04, 2003 3:23 pm

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
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)

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. » Fri Jul 04, 2003 3:31 pm

can ypu give me some example cases that went wrong

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Jul 04, 2003 4:03 pm

I forgot about one thing:
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)

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. » Fri Jul 04, 2003 6:29 pm

Oh I didn't read the part that emirp = (prime != prime reversed)

thanks I finally got accepted :wink:

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10235 wa ,,all the time ,, plizzzzzzzzzzzzzzzz help

Post by Riyad » Tue Sep 02, 2003 4:04 pm

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 :

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;
}
waiting for u r help
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

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

Post by Joseph Kurniawan » Wed Sep 03, 2003 7:25 am

Hello Riyad,
Actually this prob considered 1 as an emirp !!.
(Silly isn't it? as far as I know, 2 is the smallest prime).
Hope it helps!! :wink: :wink:
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

i got it ac , at last

Post by Riyad » Wed Sep 03, 2003 5:30 pm

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.

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

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

i got it ac , at last

Post by Riyad » Wed Sep 03, 2003 5:32 pm

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.
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

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

Post by Joseph Kurniawan » Fri Sep 05, 2003 9:39 am

Darn it. Yes, 1 is a prime not an emirp. Sorry for the wrong info :oops: :oops: :oops:
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

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

Post by Amir Aavani » Thu Oct 09, 2003 9:13 am

dear Riyad

your code have another mistake (i think), :wink:

in your code, function check, doesn't work completely right.
consider 25 as an input to this function. the output is 1.

Post Reply

Return to “Volume 102 (10200-10299)”