10235 - Simply Emirp

[nasty]

[c][cpp]

#include<stdio.h>
#include<math.h>
int chkprime(unsigned long);

int main()
{
int k=0,cnt=0,j,in;
unsigned long n,rf=0,xf,fnum[50],num;
while(scanf("%lu",&n)!=EOF)
{
if(n > 1 && n < 1000000)
{
num=n;
if(!(n%2) || !(n%3))
{
k=0;
if(n==2 || n==3)
k=1;
}
else
k=chkprime(n);
if(k==0)
{
printf("%lu is not prime.\n",num);
continue;
}
while(n!=0)
{
xf=n%10;
fnum[cnt]=xf;
n=n/10;
cnt++;
}
for(j=cnt-1,in=0;j>=0;j--,in++)
rf=rf+fnum[j]*pow(10,in);

if(!(rf%2) || !(rf%3))
{
k=0;
if(rf==2 || rf==3) k=1;
}
else
k=chkprime(rf);
if(k==0 ||(num==rf))
printf("%lu is prime.\n",num);
else
printf("%lu is emirp.\n",num);
cnt=0;
k=0;
rf=0;
}
}
return 0;
}
int chkprime(unsigned long n)
{
unsigned long d;

unsigned long i,in,p=n-1;
d=1;
if(p==1) i=1;
for(in=4;in<=2147483648;in=in*2)
if(p<in) {i=in/2;break;}
for(;i>=1;i=i/2)

{
d=((d*d)%n);
if(p&i)
d=((d*2)%n);
}
if(d!=1) return 0;
if(n==3) return 1;
else if(n==5) return 1;
for(p=3;p<=sqrt(n);p+=2)
if(!(n%p)) return 0;
return 1;

}[/cpp][/c]

[Andrew Neitsch]

You are more likely to get help if you describe your algorithm in english. Few people will have the time or courage to understand and debug your code.

[ahri]

[cpp]#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;


#define to_string(nmbr, strng) { static char _to_string_buffer[100]; sprintf( _to_string_buffer, "%d", nmbr ); (strng) = string(_to_string_buffer); }
#define to_num(strng, nmbr) sscanf( (strng).c_str(), "%Ld", &(nmbr) )

#define MAXPRIMES 10000001

#define isprime(x) (((x)==2) || (((x)&1)&&((x)>0)&&(primes[((x)-3)>>4]>>((((x)-3)>>1)&7))&1))
#define setnotprime(x) ( primes[((x)-3)>>4] = primes[((x)-3)>>4] & ~( 1 << ((((x)-3)>>1)&7) ) )
unsigned char primes[(MAXPRIMES>>4)+1];

void prime_seed() { long long i=3,j; memset(primes,~0,sizeof(primes)); while (i<MAXPRIMES) { for(j=(i<<1)+i;j<MAXPRIMES;j+=i<<1) setnotprime(j); do { i+=2; } while (!isprime(i) && i<MAXPRIMES); } }

string solution (long long n) {
long long m;
string r, temp;
to_string(n, temp);
r=temp;

if (!isprime(n)) return r+" is not prime.";

reverse(temp.begin(), temp.end());
to_num(temp, m);
if (isprime(m) && m!=n) return r + " is emirp.";
return r+ " is prime.";

}


int main () {

prime_seed();
long long n;

while(scanf("%Ld", &n)==1) cout << solution(n) << endl;


return 0;
}


[/cpp]


isprimes works perfecty, i use it very often on topcoder...
same as to_string and to_num

i'm still geting WA.
any ideas?
thanks!

[ahri]

works now, i edited the code...

[rashed_mondol]

Why WA Please Help me

#include<stdio.h>
#include<math.h>
#define type long
#define range 1000001
#define dtype char
#define prange 1000000
dtype x[range];
type reverge(type n);
void save_method(dtype x[range],type n);
void main()
{
type i,n,t;
save_method(x,prange);
while(scanf("%ld",&n)!=EOF)
{
if(x[n]==49) printf("%ld is not prime.\n",n);
else
{
t=reverge(n);
if(x[t]==0) printf("%ld is emirp.\n",n);
else printf("%ld is prime.\n",n);
}
}

}


type reverge(type n)
{
type tem,k,t,i,value;
t=log10(n);
k=t;
tem=0;
for(i=0;i<t;i++)
{
value=n%10;
n=n/10;
tem=tem+value*pow(10,k);
k--;
}
tem=tem+n;
return tem;

}
void save_method(dtype x[range],type n)
{
type j,i,tem;
x[0]=49;x[1]=49;x[2]=0;
i=4;
while(1)
{
x=49;
i=i+2;
if(i>n) break;
}
for(i=2;i<=n;i++)
{
if(x==0)
{
j=3;
tem=i*j;
while(1)
{
if(tem>n) break;
x[tem]=49;
j=j+2;
tem=i*j;

}
}
}


}

[sohel]

Consider this line from the problem statement

An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed

That means 11 is not emirp because when you reverse 11, we don't get a different prime.... numbers like 2 3 5 7 are primes not emirps.

Change this part of your code and we will get ACed.

BTW: There are other posts relating to this matter.. you should look at other posts before creating a new one.

Hope it helps.

[p!ter]

Hi!

Can enyone look at my code and tell me what is wrong.
I red all posts about this problem and i tryed all inputs and I think everything is fine!!

plz help!!!

Code: Select all

Removed after acc.....

thx in advance!!!

[mohiul alam prince]

hi
just change
for(i=2; i<=sqrt(n) + 1; ++i)

for(i=2; i<=sqrt(w) + 1; ++i)

and get AC.

MAP

[p!ter]

Hi!!!!

I changed my code and got accepted !!!!!!
Thanx very much!!!!!!!!!!!!!!!!!!!!!!
God bless u!!!!!!!!

[Iqram Mahmud]

Guys , tell me what is the wrong here?

Code: Select all

/* coded on 03.02.05
	By FAHIM, NDC                               ##10235##    */


#include <stdio.h>
#include <ctype.h>
#include <math.h>



char cnum[11];
double rev();
int check(double num);

void main(){
double num,renum;
int a,b;

while(scanf("%s",cnum)==1) {
		num=atof(cnum);
		renum=rev();
		a=check(num);
		if(a) b=check(renum);
		if(a && b && num!=renum) printf("%.0lf is erimp.\n", num);
		else if(a) printf("%.0lf is prime.\n", num);
		else printf("%.0lf is not prime.\n",num);

		}
}

double rev() {
char ch;
int i,len;

len=strlen(cnum);
for(i=0;i<len/2;i++) {
			ch=cnum[i];
			cnum[i]=cnum[len-1-i];
			cnum[len-1-i]=ch;
				}
return atof(cnum);

}

int check(double num) {
long i,j=1;
for(i=2;i<=sqrt(num); i++)  if(fmod(num,i)==0) {j=0;break;}
if(j) return 1;
else return 0;

}

[sumankar]

Two things:
1. Is using integers that difficult?Double and floating point numbers are kind of messy - so you should not be using them until and unless they are absolutely necessary - which might be causing some problem here.
2.#include<string.h> - that strlen() has no definition and can lead you to all sorts of uncalled for events.Beware!

Regards,
Suman.

P.S:If you really are dead by now, as the heading suggests, I think this post has been a waste...
[edit]
One more thing ... fmod sucks,really.I found it the hard way.And that comparison with zero(fmod(blahblah...)) is not safe etc etc

And it prints 1 is a prime!

[murkho]

Hi, Here is my code. I read post topics here of this problem. But i have none of this problems. I don't know why WA. Help me plzzzzzz

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>


int is_prime(long int num)
{

long int i,j,k;
if(num ==1) return 0;
	for(i = 2;i<=sqrt(num)+1;i++)
		if(num%i == 0)
			return 0;

return 1;

}


long int  reverse_digit(long int n)
{
char str[20];
long int ret,index= -1;
	while(n%10)
	{
	str[++index] = n%10 + 48;
	n = n/10;
	
	}
	str[++index ] =  NULL;
ret = atol(str);
return ret;

}



int main()
{

long int num,mun;
	while(scanf("%ld",&num) != EOF)
	{
		mun = reverse_digit(num);
		if(is_prime(num) && is_prime(mun) && num!= mun)
			printf("%ld is emirp.\n",num);
		else if(is_prime(num) )
			printf("%ld is prime.\n",num);
		else if(is_prime(num) ==0)
			printf("%ld is not prime.\n",num);	
	
	
	}

return 0;

}

[Raiyan Kamal]

Your program says,

2 is not prime.

[jjtse]

Try This Test Case :
Note : that 2 is not emirp, but prime!

Sample input:
2
1
10
11
71
9001
10009901
1321
1099933

Sample Output
2 is prime.
1 is prime.
10 is not prime.
11 is prime.
71 is emirp.
9001 is emirp.
10009901 is not prime.
1321 is emirp
1099933 is emirp.

Hope this Helps.
GOOD LUCK
RED SCORPION

Are you sure that 1 is prime??
Also, you forgot a '.' after your 1321 is emirp

[sakhassan]

Can anybody help me in reducing TLE


#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>

long int p[1000001];


void prim()
{

long int i,j;
int prime;


p[2]=1;
p[3]=1;
p[5]=1;
p[7]=1;
p[11]=1;

p[13]=1;
p[17]=1;
p[19]=1;
p[23]=1;
p[29]=1;

p[31]=1;
p[37]=1;
p[41]=1;
p[43]=1;
p[47]=1;

p[53]=1;
p[59]=1;
p[61]=1;
p[67]=1;
p[71]=1;

p[73]=1;
p[79]=1;
p[83]=1;
p[89]=1;
p[97]=1;

p[101]=1;



for(i=103;i<999998;i+=2)
{
prime=1;
for(j=2;j<sqrt(i)+1;j++)
{
if( !(i%j) )
{
prime = 0;
break;
}
}

if(prime)
p=1;




}
}

int main()
{


char str[80],rev[80];
long int n,nr;
int len,i,j;


prim();
while(scanf("%s",str)==1)
{
n = atoi(str);
if(p[n]==0)
printf("%ld is not prime.\n",n);
else
{
//strrev(str);
len = strlen(str);
for(i=len-1,j=0;i>=0;i--,j++)
rev[j]=str;
rev[j]='\0';
nr = atoi(rev);
if(p[nr]==1 && (strcmp(str,rev)!=0) )
printf("%ld is emirp.\n",n);
else
printf("%ld is prime.\n",n);

}
}


return 0;

}