10200 - Prime Time

[Fuad Hassan EWU]

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.

[Jan]

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.

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.

[Fuad Hassan EWU]

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

Code: Select all

AC

[Jan]

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.

[Fuad Hassan EWU]

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.

[Jan]

Try using

Code: Select all

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

Hope it helps.

[Fuad Hassan EWU]

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.

[Jan]

Check the link below..

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

[Fuad Hassan EWU]

thanks jan vai, now i am clear.

[alamgir kabir]

I got AC at last.

Code: Select all

//code removed

Thanks sapnil.

[sapnil]

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

[turcse143]

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

[ChiperOrtizII]

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.

[Jan]

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.

[tanmoy]

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