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

JWizard
New poster
Posts: 5
Joined: Mon Jul 01, 2002 4:21 pm
Contact:

Post by JWizard »

Alright:

output for 1:

1 is not prime.

output for 2:

2 is prime.

output for 13:

13 is emirp.

thanks a lot for your help

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

Same as mine except the one for input 1 (mine is prime, but it doesn't matter, as it's not an input, which is stated 1 < N < 1000000).

If you don't mind, could you send your codes through Private Message so that I can have a look at it? I am now very curious and it's interesting to me~

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

I have received your codes~

I have not taken a in-depth look at it, but I just have done an interesting thing: I use a program to generate a file consisting of 2,3,4,5,...,999999, then use this file as the input file of my program and your program. Finally, I diff the output file generated by the two program and found that..... NO DIFFERENCE (at least found by the diff program in UNIX)

I can be sure that your program is of no problem~
Or something not releted to the problem introduces the WA~ e.g. submitted with wrong problem number? Haha..... :) :)

JWizard
New poster
Posts: 5
Joined: Mon Jul 01, 2002 4:21 pm
Contact:

Post by JWizard »

I just checked and I had submitted with the right problem number .....
just resubmitted it and it works now :)
Thanks for your help

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

10235 emirp definition

Post by deddy one »

I'm a bit confused about emirp ,can anyone define emirp more
clearly???

why 2 is not emirp ?????

thx in advance.

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan »

I quote from the problem statement:
An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed
2 is not different than 2 when reversed... :wink:

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one »

thx kmhasan, that clears up the whole thing now
:D

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

10235 Emirp Why WA

Post by sohel »

if anyone can tell me why
this program is wrong
.... I would be very grateful.

#include<stdio.h>
#include<math.h>
int chkprime(unsigned long);

int main()
{
int k=0,cnt=0,j,in;
unsigned long n,rf=0,xf,fnum[50],num;
while(scanf("%lu",&n)!=EOF)
{
num=n;
if(!(n%2) || !(n%3)) {k=0;if(n==2 || n==3) k=1;}
else k=chkprime(n);
if(k==0) {printf("%lu is not prime.\n",num);continue;}
while(n!=0)
{ xf=n%10;
fnum[cnt]=xf;
n=n/10;
cnt++;
}
for(j=cnt-1,in=0;j>=0;j--,in++)
rf=rf+fnum[j]*pow(10,in);
if(!(rf%2) || !(rf%3)) {k=0;if(rf==2 || rf==3) k=1;}
else k=chkprime(rf);
if(k==0 ||(num==rf)) printf("%lu is prime.\n",num);
else printf("%lu is emirp.\n",num);
cnt=0;
k=0;
rf=0;
}
return 0;
}
int chkprime(unsigned long n)
{
unsigned long d;

unsigned long i,in,p=n-1;
d=1;
if(p==1) i=1;
for(in=4;in<=2147483648;in=in*2)
if(p<in) {i=in/2;break;}
for(;i>=1;i=i/2)

{
d=((d*d)%n);
if(p&i)
d=((d*2)%n);
}
if(d!=1) return 0;
if(n==3) return 1;
else if(n==5) return 1;
for(p=3;p<=sqrt(n);p+=2)
if(!(n%p)) return 0;
return 1;

}

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion »

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

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier »

An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed.
You should check if the mirror is different before the second prime test.
Not AC yet Image AC at last Image

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

logical error i guess. modify the following code:
code to modify:
[cpp]if(isPrime(b))
if(a!=b)
printf("%lld is emirp.\n",a);
else
printf("%lld is prime.\n",a);
[/cpp]
code to replace with:
[cpp]if(isPrime(b)) {
if(a!=b)
printf("%lld is emirp.\n",a);
else
printf("%lld is prime.\n",a);
}
else
printf("%lld is prime.\n",a);
[/cpp]
and i think you should use long instead of long long.

good luck
-sohel

lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

10235 Time Limit Exceeded

Post by lendlice »

anyone can help me
[cpp]//10235
#include<stdio.h>
#include<string.h>
main()
{
unsigned long n=0,tr1=0,tr2=0,in1=0,in2=0,i=0,j=0,num=2;
char in[100000];
while(scanf("%s",in)==1)
{
n=strlen(in);
j=n-1;
while(i<n)
{
in1=(in-'0')+in1*10;
in2=(in[j]-'0')+in2*10;
i++;
j--;
}
while(tr1==0&&num<in1)
{
if(in1%num==0)
tr1=1;
else
num++;
}
num=2;
if(in1==in2)
tr2=1;
while(tr2==0&&num<in2)
{
if(in2%num==0)
tr2=1;
else
num++;
}
if(tr1==1)
printf("%ld is not prime.\n",in1);
else if(tr1==0&&tr2==1)
printf("%ld is prime.\n",in1);
else if(tr1==0&&tr2==0)
printf("%ld is emirp.\n",in1);
tr1=0;
tr2=0;
in1=0;
in2=0;
num=2;
i=0;
}
}[/cpp]

Sebasti
New poster
Posts: 10
Joined: Sun Apr 13, 2003 11:41 pm
Contact:

Post by Sebasti »

Hi,

Change the limits of your while loops to sqrt(in1)+1 and sqrt(in2)+1.

If the TLE still, try precalc the prime numbers and put them on a big array
(sieve of eratostenes).

Bye.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

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
1 is not prime!!

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

1 is not prime!!
it doesn't matter actually. problem statement says:
Assume that 1< N< 1000000.
so, 1 is not in the judge input :)

good luck
-sohel

Post Reply

Return to “Volume 102 (10200-10299)”