OJ Board

Posted: **Thu Sep 27, 2007 4:52 pm**

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.

Posted: **Thu Sep 27, 2007 5:38 pm**

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.

Posted: **Thu Sep 27, 2007 8:51 pm**

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

Code: Select all

AC

Posted: **Fri Sep 28, 2007 8:46 am**

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.

Posted: **Sat Sep 29, 2007 9:23 pm**

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.

Posted: **Sun Sep 30, 2007 9:16 am**

Try using

Code: Select all

printf("%.2lf\n",result+1e-7);

Hope it helps.

Posted: **Sun Sep 30, 2007 12:04 pm**

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.

Posted: **Sun Sep 30, 2007 12:11 pm**

Check the link below..

http://online-judge.uva.es/board/viewto ... c&start=27
Hope it helps.

Posted: **Sun Sep 30, 2007 2:33 pm**

thanks jan vai, now i am clear.

Posted: **Fri Oct 26, 2007 6:08 pm**

I got AC at last.

Code: Select all

//code removed

Thanks sapnil.

Posted: **Fri Oct 26, 2007 6:37 pm**

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

Posted: **Tue Feb 26, 2008 12:10 pm**

thanks jan vai. at last i got AC.
i just forgot a small precision error.

Posted: **Mon Apr 14, 2008 7:52 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

Please Help Cristian Ortiz Venezuela

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;
Procedure Load;
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);
  Load;
  while (Not Eof) Do
  Begin
     Readln(a,b);
     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.

Posted: **Mon Apr 14, 2008 11:03 pm**

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.

Posted: **Thu Jun 26, 2008 3:01 am**

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

OJ Board

10200 - Prime Time

...

Re: ...

plz help

..

...

..

10200 WA please help

Re: 10200 - Prime Time

10200 PRIME TIME