## 10235 - Simply Emirp

Moderator: Board moderators

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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]

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

### 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=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<=num;i++)
{

if(primes==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.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
10235 is 'Simply Emirp'..
.. i don't think you are mentioning the right problem !!!

New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
yeah---------
It's a great mistake............
I have edited the code......
now whats the wrong????????????

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
#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.

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

### 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=true;
prime=false;
prime=false;
int m=(int)sqrt(n);
for(int i=2;i<=m;i++)
if(prime)
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...

Tahasin
New poster
Posts: 6
Joined: Tue Jun 27, 2006 7:19 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;
}

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### 10235

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Notice
Emirp is a prime number that produces different prime number when reversed not the same.
Okay?

Hope this helps! Keep posting.
Solving for fun..

razor_blue
New poster
Posts: 27
Joined: Mon Nov 27, 2006 4:44 am
Location: Indonesia

New poster
Posts: 13
Joined: Sun Mar 04, 2007 8:40 pm
Here:

Code: Select all

`````` 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);``````
I don't think you need to check if b==d , also see if (prime(b)==0 not b.
(If i get right when prime(n)==0 then n=0)
Do this:
if(prime(b)!=0) -> No prime
else if(prime(b)==0 && prime(d)!=0) -> Is prime
else -> Is emirp
I don't think you need long int, i use simple int and got AC
/*No Comment*/

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm
i tried but

WA
if anyone check why
this is
WA
Last edited by bishop on Mon Jun 11, 2007 8:18 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Check the following line.

Code: Select all

``else if(prime(n) || prime(rev))``
29 is a prime, isn't it?
Ami ekhono shopno dekhi...
HomePage

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm
only if reverse number is prime
result is not prime
i got it

thanx
a lot

``````Hmmmmmmm, AC