10235 - Simply Emirp

[lendlice]

thanks
i got ac

[r.z.]

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

ups I pasted it twice.....

[zsepi]

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

[r.z.]

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]

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

[r.z.]

can ypu give me some example cases that went wrong

[Dominik Michniewski]

I forgot about one thing:
think about numbers which have reverse the same as start number

Best regards
DM

[r.z.]

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

thanks I finally got accepted

[Riyad]

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

[Joseph Kurniawan]

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

[Riyad]

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

[Riyad]

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

[Joseph Kurniawan]

Darn it. Yes, 1 is a prime not an emirp. Sorry for the wrong info

[Amir Aavani]

dear Riyad

your code have another mistake (i think),

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