10235 - Simply Emirp

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

Moderator: Board moderators

Postby p!ter » Tue Feb 08, 2005 6:38 pm

Hi!!!!

I changed my code and got accepted !!!!!!
Thanx very much!!!!!!!!!!!!!!!!!!!!!!
God bless u!!!!!!!! :P
p!ter
New poster
 
Posts: 11
Joined: Thu Nov 18, 2004 8:55 pm

10235 - I am dead!

Postby Iqram Mahmud » Tue Mar 29, 2005 1:22 pm

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

Postby sumankar » Tue Mar 29, 2005 2:12 pm

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... :wink:
[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!
sumankar
A great helper
 
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

10235 -WA help me plzzzzzzzzzzzzzzzz

Postby murkho » Mon Apr 18, 2005 5:31 pm

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

Postby Raiyan Kamal » Tue Apr 19, 2005 3:23 pm

Your program says,
2 is not prime.
Raiyan Kamal
Experienced poster
 
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh

Postby jjtse » Thu Dec 01, 2005 8:58 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. :lol:

Hope this Helps.
GOOD LUCK
RED SCORPION :D



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
Location: Nevada, US

10235

Postby sakhassan » Thu Jun 15, 2006 8:29 am

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

Postby 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]
User avatar
the LA-Z-BOy
Learning poster
 
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh

10235 whats wrong???????

Postby 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[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.
SHAHADAT
New poster
 
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

Postby sohel » Sun Jun 25, 2006 12:34 pm

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

Postby SHAHADAT » Thu Jun 29, 2006 10:15 am

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

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

10235 :WA HELP

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

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

10235

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

please use long int .
mak(cse_DU)
Learning poster
 
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

PreviousNext

Return to Volume CII

Who is online

Users browsing this forum: No registered users and 1 guest