10235 - Simply Emirp

All about problems in Volume CII. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

10235 tell me why wrong answer help me out

Postby 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]
nasty
New poster
 
Posts: 4
Joined: Sat Jul 10, 2004 11:27 am
Location: pakistan

Postby 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.
Andrew Neitsch
New poster
 
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

10235 WA

Postby 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

Postby ahri » Mon Aug 23, 2004 3:10 am

works now, i edited the code...
ahri
New poster
 
Posts: 3
Joined: Fri Jan 16, 2004 2:12 pm

10235 WA Help!!!

Postby 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[i]=49;
i=i+2;
if(i>n) break;
}
for(i=2;i<=n;i++)
{
if(x[i]==0)
{
j=3;
tem=i*j;
while(1)
{
if(tem>n) break;
x[tem]=49;
j=j+2;
tem=i*j;

}
}
}


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

oopsi

Postby 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:
User avatar
sohel
Guru
 
Posts: 859
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

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

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

Postby 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
User avatar
mohiul alam prince
Experienced poster
 
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

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

Hi!!!!

I changed my code and got accepted !!!!!!
Thanx very much!!!!!!!!!!!!!!!!!!!!!!
God bless u!!!!!!!! :P
p!ter
New poster
 
Posts: 11
Joined: Thu Nov 18, 2004 8:55 pm

10235 - I am dead!

Postby 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>
Iqram Mahmud
New poster
 
Posts: 2
Joined: Tue Mar 29, 2005 1:09 pm
Location: Dhaka , BD

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

10235 -WA help me plzzzzzzzzzzzzzzzz

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

}


murkho
New poster
 
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

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

Your program says,
2 is not prime.
Raiyan Kamal
Experienced poster
 
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh

Postby 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
jjtse
Learning poster
 
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US

10235

Postby 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[i]=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[i];
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;

}
sakhassan
Experienced poster
 
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

PreviousNext

Return to Volume CII

Who is online

Users browsing this forum: No registered users and 1 guest