Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

look at this

Posted by cyron16 at 2005-10-29 01:06:25 on Problem 2689
it builds the prime numbers in P and the number of them lgP
it marks the elements of tinterval lo..hi which are not prime
it build the D vector with the prime numbers from lo..hi with length lgD
could please someone help me with the debug?:(


const maxn=1000002;maxp=6550;oo=maxlongint;
var V:array[0..maxn]of boolean;
    P:array[1..maxp]of longint;
    D:array[1..maxn]of longint;
   Min1,Min2,Max1,Max2,aux,lo,hi,j,i,lgp,lgd:longint;
   Procedure BuildPrime;
   var ok:boolean;
   begin
      lgp:=1;P[1]:=2;
      for i:=1 to (1 shl 15) do
      begin
         P[lgp+1]:=i*2+1;
         ok:=true;
         j:=1;
         while (sqr(P[j])<=P[lgp+1])and (j<=lgp)and ok do
         begin
            ok:=ok and (P[lgp+1]mod P[j]<>0);
            inc(j);
         end;
         if ok then inc(lgp);
      end;
   end;
   function max(a,b:int64):int64;begin if a>b then max:=a else max:=b;end;
   procedure BuildErastone;
   begin
      i:=1;
      while int64(sqr(P[i]))<=hi do
      begin
         if Lo mod P[i]=0 then aux:=0 else aux:=1;
         for j:=max((lo div P[i]+aux),2) to (hi div P[i]) do
            V[j*int64(P[i])-lo]:=true;
         inc(i);
      end;
   end;
   procedure BuildAll;
   begin
      lgd:=0;
      for i:=lo to hi do if not V[i-lo] then begin inc(lgd);D[lgd]:=i;end;
   end;
begin
   BuildPrime;
   readln(lo,hi);
   BuildErastone;
   BuildAll;
   if lgd<2 then writeln('There are no adjacent primes.') else
   begin
      Min1:=0;Min2:=oo;Max1:=0;Max2:=0;
      for i:=1 to lgd-1 do
      begin
         if Min2-Min1>D[i+1]-D[i] then begin Min2:=D[i+1];Min1:=D[i];end;
         if Max2-Max1<D[i+1]-D[i] then begin Max2:=D[i+1];Max1:=D[i];end;
      end;
      writeln(Min1,',',Min2,' are closest, ',max1,',',max2,' are most distant.');
   end;
end.


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator