10200 - Prime Time

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

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

...

that means jan vai you are telling that i will have to generate prime upto sqrt(100010041) and collect hose primes and then check whether 100010041 is prime or not in terms of worst case by checking whether 100010041 is divisible by any prime number upto sqrt(100010041), am i right? bt jan vai why my code is giving WA. i use more memory then it should have been given me memory limit exceed. plz explain this. thank you.
Eagle er moto daana meley urbo

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: ...

Fuad Hassan EWU wrote:that means jan vai you are telling that i will have to generate prime upto sqrt(100010041) and collect hose primes and then check whether 100010041 is prime or not in terms of worst case by checking whether 100010041 is divisible by any prime number upto sqrt(100010041), am i right?
Yes you are right.
Fuad Hassan EWU wrote: bt jan vai why my code is giving WA. i use more memory then it should have been given me memory limit exceed. plz explain this. thank you.
You can post your new code. Yes, you should have given MLE. But I dont know why WA was given.
Ami ekhono shopno dekhi...
HomePage

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

plz help

jan vai i chage the code as bellow, now i am again having WA.

Code: Select all

AC
Last edited by Fuad Hassan EWU on Sun Sep 30, 2007 12:05 pm, edited 3 times in total.
Eagle er moto daana meley urbo

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Two things you should remember...

1. sqrt() is a slow function. So, you can store the value of sqrt(f) in a varibale, cause then you dont have to use sqrt(f) all the time.

2. Precalculate all the numbers. Suppose A[X] will store how many primes you have found using n = 0 to X. So, before taking any input, build the array A. Then each query can be answered in just O(1) time.

Hope these help.
Ami ekhono shopno dekhi...
HomePage

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

..

jan vai i edited the code above, now i am getting WA. i am not finding the way. how many days i will have to hang around with this simple problem.     plz help me. thank you.
Eagle er moto daana meley urbo

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try using

Code: Select all

printf("%.2lf\n",result+1e-7);
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

...

Yes jan vai Finally it is accepted. thank you very much. but if u plz explain me why i had to use result+1e-7, i mean i want to know the reason behind it. thank you again.
Eagle er moto daana meley urbo

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

http://online-judge.uva.es/board/viewto ... c&start=27
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

..

thanks jan vai, now i am clear.
Eagle er moto daana meley urbo

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

I got AC at last.

Code: Select all

//code removed
Thanks sapnil.
Last edited by alamgir kabir on Sun Oct 28, 2007 1:42 pm, edited 2 times in total.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Try this cases

Code: Select all

1 10000
1 1
2 2
1 2
output:
41.48
100.00
100.00
100.00
Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
thanks jan vai. at last i got AC.
i just forgot a small precision error.
''I want to be most laziest person in the world''

ChiperOrtizII
New poster
Posts: 2
Joined: Mon Apr 14, 2008 7:44 pm
Hi This Is My First Entry At The Forum I Dont Know If I Did It Wrong.... Can SomeBody Give Some Tricks About 10200 Prime Time I´m Getting TL IN Pascal.. Pascal Was My First Languague To Program But I dont use It Often Later I Use Java Instead

Code: Select all

{\$N+}
Const
LimiA = 10005;
LimiB = 1230;
Var
Vec    :  Array[1..LimiA] Of boolean;
Primes : Array[1..LimiB] Of Integer;
PosA,a,b : Integer;
Archivo : Text;
Sol     : double;
I,SolA    : LongInt;
Opc : LongInt;
Sw : boolean;
Car : Char;
Procedure Sieve(L:Integer;U:Integer);
Var
I,J:Integer;
AuxCon : Integer;
Begin
For I:= L To U Do
If (Not Vec[i]) Then
Begin
AuxCon:= (I+I);
While(AuxCon <= U) Do
Begin
Vec[AuxCon] := True;
AuxCon := AuxCon + i;
End;
End;
End;
Var
I,Pos : Integer;
Begin
Pos := 1;
For I:= 2 To LimiA Do
Begin
if (Not Vec[i]) Then
Begin
Primes[Pos]:= i;
Pos:= Pos+1;
End;
End;
End;

Function Solucion(L:Integer; U: Integer) : Integer;
Var
I,Aux,Sol: Integer;
Begin
PosA:= 0;
Sol:= 0;
For I:= L To U Do
Begin
Aux := (i*i)+i+41;
PosA:= PosA+1;
if (Not Vec[Aux]) Then Sol:= Sol+1;
End;
Solucion:= Sol;
End;

Function IsPrime(Num:LongInt) : Boolean;
Var
I,x : Integer;
Sw : Boolean;
Begin
Sw:= true;
For I:= 1 To 1229 Do
Begin
if (Num Mod Primes[i] = 0) Then
Begin
Sw:= false;
break;
End;
End;
IsPrime:= Sw;
End;

Begin
Sieve(2,LimiA);
while (Not Eof) Do
Begin
If ((b*b)+b+41 <= LimiA) Then
Sol:= (Solucion(a,b)*100)/PosA
Else
Begin
SolA:= 0; PosA := 0;
for I:= A To B Do
Begin
Opc := I;
Opc := I*I;
Opc := Opc + i+41;
Sw:= IsPrime(Opc);
PosA:= PosA+1;
if (Sw) Then SolA:= SolA+1;
End;
Sol := (SolA*100)/PosA;
End;
Writeln(Sol:0:2);
End;
End.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 10200 - Prime Time

Read previous threads. For each query you don't have to run a loop like..

Code: Select all

for I:= A To B Do
Before taking inputs make an array say M[]. M[x] will store the number of primes (using the formula) from 0 to x. Then you can answer each query easily.
Ami ekhono shopno dekhi...
HomePage

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

10200 PRIME TIME

SOMEBODY PLEASE HELP ME IT IS WA WHY ?
HERE IS MY CODE .IT PASSES ALL THE INPUT VALUES WHICH I CAN FIND.
PLEASE HELP ME #include<stdio.h>
#include<math.h>
int store[10002+5];
int is_prime(int a)
{
int c;
if (a==1) return 0;
if (a==2) return 1;
if (a%2==0)return 0;
c= int(sqrt(a));
int x;
x=int(c);
for(x=3;x<=c;x+=2)
if(a%x==0)return 0;
return 1;
}
int is_prime(int a);
int main()
{
int a,b,c;
int l;
int sum;
float y;
float k;
for(a=0;a<=10002;a++)
{
l=int(pow(a,2));
if(is_prime(l+a+41)==1)store[a]=1;
else store[a]=0;
}

while(scanf("%d %d",&a,&b)==2)
{ sum=0;
for(c=a;c<=b;c++)
{
if(store[c]==1)sum++;

}
int g=b-a+1;
k=float(sum*100.00);
y=float(k/g);
printf("%2.2f\n",y);
}
return 0;
}