10235 - Simply Emirp
Moderator: Board moderators
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]
#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]
-
- New poster
- Posts: 43
- Joined: Fri Jun 25, 2004 9:37 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!
#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!
-
- New poster
- Posts: 2
- Joined: Wed Nov 10, 2004 8:26 am
- Location: Bangladesh
10235 WA Help!!!
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;
}
}
}
}
#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
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.
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.

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!!!
thx in advance!!!
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)
-
- 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>
#include <smile.h>
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!
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!
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;
}
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- 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
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;
}

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