10235 - Simply Emirp

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

}

[the LA-Z-BOy]

Consider these codes in your prime generating ...

Code: Select all

  for(i=103;i<999998;i+=2)
  {
    prime=1;
    for(j=2;j<sqrt(i)+1;j++)
  {
  ....

These are too costly ... because for each i you call sqrt() function i^0.5 times!!! sqrt() is slow and calling it so many times would get you TLE. You can avoid these by changing it to

Code: Select all

  for(i=103;i<999998;i+=2)
  {
    prime=1;
    int z = sqrt(i)+1;
    for(j=2;j<z;j++)
  {
  ....

This code is same but calls sqrt() only once for each i. Also there is way out not using sqrt() at all

Code: Select all

  for(i=103;i<999998;i+=2)
  {
    prime=1;
    for(j=2;j*j<=i;j++)
  {
  ....

These are enough for getting this problem Accepted, but this is not how you can generate primes faster. You would stuck on larger limits on other problems... You can check this board for very very efficient prime generating alogrithms... Sieve or Eratosthenes maybe....
Keep on rollin'
Greets.

[SHAHADAT]

I don't know whats wrong with this.....
I need some sample input output.............
#include<stdio.h>
#include<math.h>
#define LIMIT 1000000
#define SIZE 1000000
#define BLOCK sizeof(long)
long prime_num,primes[SIZE],temp[LIMIT/BLOCK/2+1];
long is_prime(long num)
{
num=(num-1)/2;
if(num%BLOCK==0)return (!(temp[num/BLOCK-1]&1));
else return(!(temp[num/BLOCK]&(1<<(BLOCK-num%BLOCK))));
}
void seive()
{
long i,j,k,loc,loop;
prime_num=0;
if(LIMIT<=1) return ;

for(i=0,k=LIMIT/BLOCK/2;i<k;i++)
{
temp[i]=0;
}
for(i=3,loop=(int)sqrt(LIMIT);i<=loop;i+=2)
{
if(is_prime(i))
{
for(j=i,k=LIMIT/i;j<=k;j+=2)
{
loc=(i*j-1)/2;
if(loc%BLOCK==0)temp[loc/BLOCK-1]|=1;
else temp[loc/BLOCK]|=(1<<(BLOCK-loc%BLOCK));
}
}
}
int l=-1,m=-1;
primes[++prime_num]=1;
for(i=3,primes[++prime_num]=2;i<=LIMIT;i+=2)
{
if(is_prime(i))
{

primes[++prime_num]=i;

}
}
return;
}

long rev(long n){
long l,d,e,f;
long a,j;
long m;
m=n;
a=log10(n)+1;
f=0;
for(j=1;j<=a;j++)
{
d=fmod(m,10);
m=m/10;
l=pow(10,a-j);
e=l*d;
f=f+e;
}

return f;
}

int main()
{
seive();
long num,flag;
long temp, i,j;
while(scanf("%ld",&num)==1)
{
flag=1;
if(num==1)
{
continue;
}
else
{
for(i=1;primes[i]<=num;i++)
{

if(primes[i]==num)
{
flag=0;

temp=(long)(rev(num));
for(j=1;temp>=primes[j];j++)
{

}

if(temp==primes[j-1])
{
printf("%ld is emirp.\n",num);
break;
}

else
{
printf("%ld is prime.\n",num);
break;
}
}

}

if(flag==1)
{
printf("%ld is not prime.\n",num);

}
}

}
return 0;
}

[sohel]

10235 is 'Simply Emirp'..
.. i don't think you are mentioning the right problem !!!

[SHAHADAT]

yeah---------
It's a great mistake............
I have edited the code......
now whats the wrong????????????

[sohel]

#1. Use Code tag when posting codes.

#2. There are plenty of discussions about this prob in other threads.. please search for those before creating a new thread.

#3. For this problem, it says an emirp is a prime that produces a different prime when reversed... so cases such as 11 isn't emirp since it doesn't produce a different prime.. REV(11) = 11.

Hope it helps.

[akdwivedi]

this is my code.......I am no getting..where I am Wrong...any body help..plz.............

#include<iostream>
#include<math.h>
#include<cstdio>
using namespace std;
int main()
{
int n=1000000;
bool *prime =new bool[n+1];
for(int i=0;i<=n;i++)
prime[i]=true;
prime[0]=false;
prime[1]=false;
int m=(int)sqrt(n);
for(int i=2;i<=m;i++)
if(prime[i])
for(int k=i*i;k<=n;k+=i)
prime[k]=false;

long long int x;
while(scanf("%lld",&x)+1){
if(!prime[x])
printf("%lld is not prime.\n",x);
else if(prime[x]){
long long int y=0,ans=x;
while(x!=0){
y=y*10+x%10;
x=x/10;
}
if(prime[y])
printf("%lld is emirp.\n",ans);
else if(!prime[y])
printf("%lld is prime.\n",ans);
}
}
return 0;
}

[Tahasin]

#include<stdio.h>
#include<math.h>
int prime(int k)
{
int t,i,p=1;
t=sqrt(k);
for(i=2;i<=t;i++)if(k%i==0)p=0;
if(p)return k;else return 0;
}
main()
{
int a,b,c,d;
while((scanf("%d",&a))==1)
{
d=0;
b=a;
do
{
c=a%10;
d=d*10+c;
a/=10;
}while(a!=0);
if(b==d && prime(b)==b)printf("%d is prime.\n",b);
else if(prime(b)==b && prime(d)==d)printf("%d is emirp.\n",b);
else if(prime(b)==b || prime(d)==d)printf("%d is prime.\n",b);
else printf("%d is not prime.\n",b);
}
return 0;
}

[mak(cse_DU)]

please use long int .