10235 - Simply Emirp

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

[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=true;
prime[0]=false;
prime[1]=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;
}

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

[linux]

Notice

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

Okay?

Hope this helps! Keep posting.

[razor_blue]

Thank you linux, your clue is very helpful...

[KaDeG]

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

[bishop]

i tried but

WA
if anyone check why
this is
WA

[Jan]

Check the following line.

Code: Select all

else if(prime(n) || prime(rev))

29 is a prime, isn't it?

[bishop]

only if reverse number is prime
result is not prime
i got it

thanx
a lot

[Bad Boy]

Why it is wrong,

Code: Select all

Hmmmmmmm, AC