## 10235 - Simply Emirp

Moderator: Board moderators

nasty
New poster
Posts: 4
Joined: Sat Jul 10, 2004 11:27 am
Location: pakistan

### 10235 tell me why wrong answer help me out

[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
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
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
New poster
Posts: 3
Joined: Fri Jan 16, 2004 2:12 pm

### 10235 WA

[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
New poster
Posts: 3
Joined: Fri Jan 16, 2004 2:12 pm
works now, i edited the code...

rashed_mondol
New poster
Posts: 2
Joined: Wed Nov 10, 2004 8:26 am

### 10235 WA Help!!!

#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;

}
}
}

}
Acm Boss

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### oopsi

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
New poster
Posts: 11
Joined: Thu Nov 18, 2004 8:55 pm

### 10235->Simply Emirp Why WA?!!!!!!!!!!!!!!!!!!!!!!!!

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.....
``````
Last edited by p!ter on Tue Feb 08, 2005 6:42 pm, edited 1 time in total.

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
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
New poster
Posts: 11
Joined: Thu Nov 18, 2004 8:55 pm
Hi!!!!

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

Iqram Mahmud
New poster
Posts: 2
Joined: Tue Mar 29, 2005 1:09 pm
Location: Dhaka , BD

### 10235 - I am dead!

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;

}
``````
Fahim
#include <smile.h>

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
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...

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
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

### 10235 -WA help me plzzzzzzzzzzzzzzzz

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
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
2 is not prime.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Contact:
Red Scorpion wrote: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
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### 10235

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;

}