## 10235 - Simply Emirp

Moderator: Board moderators

Hi!!!!

I changed my code and got accepted !!!!!!
Thanx very much!!!!!!!!!!!!!!!!!!!!!!
God bless u!!!!!!!!
p!ter
New poster

Posts: 11
Joined: Thu Nov 18, 2004 8:55 pm

### 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>
Iqram Mahmud
New poster

Posts: 2
Joined: Tue Mar 29, 2005 1:09 pm
Location: Dhaka , BD

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!
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

### 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;}`
murkho
New poster

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

2 is not prime.
Raiyan Kamal
Experienced poster

Posts: 106
Joined: Thu Jan 29, 2004 12:07 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.

Hope this Helps.
GOOD LUCK
RED SCORPION

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

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

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.
Istiaque Ahmed [the LA-Z-BOy]

the LA-Z-BOy
Learning poster

Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm

### 10235 whats wrong???????

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;
}
Last edited by SHAHADAT on Thu Jun 29, 2006 10:14 am, edited 1 time in total.
New poster

Posts: 23
Joined: Thu Jun 22, 2006 8:55 am

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

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

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

Posts: 23
Joined: Thu Jun 22, 2006 8:55 am

#1. Use Code tag when posting codes.

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

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### 10235 :WA HELP

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;
}
Programming...
akdwivedi
New poster

Posts: 2
Joined: Mon Jun 26, 2006 8:17 am

### 10235 WA

#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;
}
Tahasin
New poster

Posts: 6
Joined: Tue Jun 27, 2006 7:19 am

### 10235

mak(cse_DU)
Learning poster

Posts: 72
Joined: Tue May 30, 2006 5:57 pm