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

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

10235 tell me why wrong answer help me out

Post by nasty » Mon Jul 19, 2004 3:09 pm

[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

Post by Andrew Neitsch » Mon Jul 26, 2004 11:34 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

Post by ahri » Mon Aug 23, 2004 2:29 am

[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

Post by ahri » Mon Aug 23, 2004 3:10 am

works now, i edited the code...

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

10235 WA Help!!!

Post by rashed_mondol » Tue Dec 21, 2004 11:41 am

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;

}
}
}


}
Acm Boss

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

oopsi

Post by sohel » Tue Dec 21, 2004 12:05 pm

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

p!ter
New poster
Posts: 11
Joined: Thu Nov 18, 2004 8:55 pm

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

Post by p!ter » Sat Feb 05, 2005 1:58 pm

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

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue Feb 08, 2005 9:10 am

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

Post by p!ter » Tue Feb 08, 2005 6:38 pm

Hi!!!!

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

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

10235 - I am dead!

Post by Iqram Mahmud » Tue Mar 29, 2005 1:22 pm

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:

Post by sumankar » Tue Mar 29, 2005 2:12 pm

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

10235 -WA help me plzzzzzzzzzzzzzzzz

Post by murkho » Mon Apr 18, 2005 5:31 pm

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
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Tue Apr 19, 2005 3:23 pm

Your program says,
2 is not prime.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Thu Dec 01, 2005 8:58 pm

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

Hope this Helps.
GOOD LUCK
RED SCORPION :D

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

Post by sakhassan » Thu Jun 15, 2006 8:29 am

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;

}

Post Reply

Return to “Volume 102 (10200-10299)”