10235 - Simply Emirp

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

Moderator: Board moderators

Post Reply
User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Thu Jun 15, 2006 5:17 pm

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]

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

10235 whats wrong???????

Post by SHAHADAT » Sun Jun 25, 2006 10:23 am

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jun 25, 2006 12:34 pm

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

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

Post by SHAHADAT » Thu Jun 29, 2006 10:15 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Jun 29, 2006 1:31 pm

#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
New poster
Posts: 2
Joined: Mon Jun 26, 2006 8:17 am

10235 :WA HELP

Post by akdwivedi » Fri Jun 30, 2006 8:37 pm

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

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

10235 WA

Post by Tahasin » Thu Aug 17, 2006 2:09 pm

#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
Location: bangladesh

10235

Post by mak(cse_DU) » Tue Sep 05, 2006 4:00 pm

please use long int .

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

10235 WA Reply.

Post by linux » Thu Sep 07, 2006 7:32 am

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

Post by razor_blue » Wed Nov 29, 2006 5:22 am

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

User avatar
KaDeG
New poster
Posts: 13
Joined: Sun Mar 04, 2007 8:40 pm

Post by KaDeG » Wed Apr 11, 2007 9:01 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

Post by bishop » Mon Jun 11, 2007 12:51 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jun 11, 2007 7:45 pm

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

Post by bishop » Mon Jun 11, 2007 8:19 pm

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

thanx
a lot

Bad Boy
New poster
Posts: 4
Joined: Fri Jul 13, 2007 5:17 am
Location: CSE, DU(13th)

Post by Bad Boy » Fri Jul 13, 2007 10:16 am

Why it is wrong,

Code: Select all

Hmmmmmmm, AC
Last edited by Bad Boy on Mon Jul 16, 2007 5:17 pm, edited 2 times in total.

Post Reply

Return to “Volume 102 (10200-10299)”