Program testujący pierwszość liczby

// reprezentacja liczby (opis wiersza tablicy liczby):

// na pozycji -1 jest liczba zajętych komórek (liczonych od 0)

// na następnych zapisana jest sama liczba, na zasadzie a[0]+10000*a[1]+...

// podczas obliczeń w zerowym wierszu zapisana jest sprawdzana liczba,

// w pierwszym i drugim są liczby określające zakres przeszukiwania,

// pozostałe służą do obliczeń

local liczby[0..16,-1..32];

 

// wejściowa liczba (jak wyżej, ale jedna więc bez tablicy)

shared liczba[-1..32];

// ilość procesorów do uruchomienia

shared proc_number;

// tablica wyników - interpretacja jak powyżej

shared wyniki[0..63,-1..32];

// tablica pomocnicza

shared zakresy[0..64,-1..32];

 

local proc;

 

//----------------------------------

// pomocnicza funkcja służąca do przepisania liczby z jednego wiersza do

// drugiego

function przepisz(a,b)

begin

memcopy(liczby[a],liczby[b],34);

end;

//----------------------------------

// funkcja tworząca liczbę w postaci tablicowej z liczby podanej jako parametr

function na_tablice(x,c)

local i;

begin

for i:=-1 to 32 do liczby[c,i]:=0;

i:=0;

while x>0 do

begin

liczby[c,i]:=x%10000;

x:=x/10000;

i:=i+1;

end;

liczby[c,-1]:=i;

end;

//----------------------------------

// funkcja sprawdzająca czy dana liczba (tablica) jest zerem

function zero(a)

begin

if liczby[a,-1]=0 then return 1;

else return 0;

end;

//----------------------------------

// funkcja porównująca dwie liczby

// zwraca odpowiednio <0, 0, >0 jeśli a<b, a=b, a>c

function porownaj(a,b)

local i;

begin

  if liczby[a,-1]<>liczby[b,-1] then return liczby[a,-1]-liczby[b,-1];

  for i:=liczby[a,-1]-1 downto 0 do

    if liczby[a,i]<>liczby[b,i] then return liczby[a,i]-liczby[b,i];

  return 0;

end;

//----------------------------------

// dodaje dwie liczby do siebie (a+b->c)

function dodaj(a,b,c)

local d;

local i;

local cn;

local p;

begin

if liczby[a,-1]>liczby[b,-1] then d:=liczby[a,-1];

else d:=liczby[b,-1];

p:=0;

for i:=0 to d-1 do

begin

cn:=liczby[a,i]+liczby[b,i]+p;

liczby[c,i]:=cn%10000;

p:=cn/10000;

end;

if p>0 then begin liczby[c,d]:=p; liczby[c,-1]:=d+1; end;

else liczby[c,-1]:=d;

end;

//----------------------------------

// "udziwnione" dodawanie

function dodaj1(a,b,n,c)

local i;

local cn;

local p;

begin

przepisz(a,c);

cn:=liczby[c,n]+b;

liczby[c,n]:=cn%10000;

if cn>10000 then

begin

p:=cn/10000; i:=n+1;

while p>0 do

begin

cn:=liczby[c,i]+p;

liczby[c,i]:=cn%10000;

p:=cn/10000;

i:=i+1;

end;

if i>liczby[c,-1] then liczby[c,-1]:=i;

end;

end;

//----------------------------------

// odejmuje od siebie dwie liczby i zwraca 0 albo, jeśli a<b, zwraca -1

function odejmij(a,b,c)

local i;

local p;

local d;

local cn;

begin

for i:=-1 to 32 do liczby[c,i]:=0;  

if porownaj(a,b)<0 then return -1;

d:=liczby[a,-1]-1;

p:=0;

for i:=0 to d do

begin

cn:=liczby[a,i]-liczby[b,i]-p;

if cn<0 then begin cn:=cn+10000; p:=1; end;

else p:=0;

liczby[c,i]:=cn;

end;

i:=d;

while liczby[c,i]=0 and i>0 do i:=i-1;

if i=0 and liczby[c,0]=0 then liczby[c,-1]:=0;

else liczby[c,-1]:=i+1;   

return 0;

end;

//----------------------------------

// mnoży podaną liczbę przez 10 (przesunięcie w lewo o jedną cyfrę)

function razy10(a,c)

local i;

local p;

local cn;

begin

p:=0;

for i:=0 to liczby[a,-1]-1 do

begin

cn:=liczby[a,i]*10+p;

liczby[c,i]:=cn%10000;

p:=cn/10000;

end;

if p>0 then begin liczby[c,i]:=p; liczby[c,-1]:=i+1; end;

else liczby[c,-1]:=i;

end;

//----------------------------------

// analogiczne dzielenie przez 10

function dziel10(a,c)

local i;

local p;

local cn;

local d;

begin

p:=0; d:=liczby[a,-1];

for i:=d-1 downto 0 do

begin

cn:=liczby[a,i]+10000*p;

liczby[c,i]:=cn/10;

p:=cn%10;

end;

if liczby[c,d-1]=0 then liczby[c,-1]:=d-1;

else liczby[c,-1]:=d;

end;

//----------------------------------

// dzieli liczbę w postaci tablicowej przez liczbę całkowitą

function podziel1(a,b,c)

local k;

local cn;

local p;

local i;

begin

k:=11;

przepisz(a,k);

for i:=-1 to 32 do liczby[c,i]:=0;

p:=0;

for i:=liczby[a,-1]-1 downto 0 do

begin

cn:=(10000*p+liczby[k,i])/b;

liczby[c,i]:=cn;

p:=(10000*p+liczby[k,i])-b*cn;

end;

i:=liczby[a,-1]-1;

while i>=0 and liczby[c,i]=0 do i:=i-1;

if i=0 and liczby[c,0]=0 then liczby[c,-1]:=0;

else liczby[c,-1]:=i+1;

return p;     // reszta z dzielenia

end;

//----------------------------------

// oblicza resztę z dzielenia

function reszta(a,b,r)

local i1;

local i2;

local j1;

local j2;

local f;

begin

i1:=11; i2:=12;

przepisz(b,i1);

j1:=13; j2:=14;

przepisz(a,j1);

f:=0;

do

begin

razy10(i1,i2);

if porownaj(a,i2)>=0 then

begin i1:=i2; if i1=11 then i2:=12; else i2:=11; end;

else f:=1;

end;

while f=0;

// teraz i1<=a ale 10*i1>a

do

begin

f:=0;

do

if odejmij(j1,i1,j2)=0 then

begin j1:=j2; if j1=13 then j2:=14; else j2:=13; end;

else f:=1;

while f=0;

dziel10(i1,i2);

i1:=i2; if i1=11 then i2:=12; else i2:=11;

end;

while porownaj(b,i1)<=0;

// teraz na j1 jest reszta z dzielenia

przepisz(j1,r); end;

//----------------------------------

// główna pętla programu procesora wirtualnego

function testuj()

local i1;

local i2;

begin

i1:=2;

i2:=3;

while porownaj(1,i1)>=0 do

begin

reszta(0,i1,4);

if zero(4)=1 then return i1;

dodaj1(i1,2,0,i2);

i1:=i2; if i1=2 then i2:=3; else i2:=2;

end;

return 0;

end;

//----------------------------------

// funkcja przygotowująca do obliczeń (procesor wirtualny)

// i je rozpoczynająca

function przygotuj()

local wynik;

begin

// przepisanie danych wejściowych do pamięci lokalnej

blockread(liczba,liczby[0],34);

// przepisanie zakresów obliczeń

blockread(zakresy[proc],liczby[2],34);

blockread(zakresy[proc+1],liczby[1],34);

// samo obliczenie

wynik:=testuj();

if wynik>0 then blockwrite(liczby[wynik],wyniki[proc],34);

end;

//----------------------------------

// funkcja służąca do ograniczenia przestrzeni przeszukiwanych liczb

function ogranicz(a,c)

local i1;

local i2;

local an;

local cn;

local i;

begin

i:=(liczby[a,-1]-1)*4;

if i<8 then

begin

for i:=-1 to 32 do liczby[c,i]:=0;

cn:=liczby[a,0]+liczby[a,1]*10000;

cn:=sqrt(cn)+1;

liczby[c,0]:=cn%10000;

liczby[c,1]:=cn/10000;

if liczby[c,1]=0 then liczby[c,-1]:=1; else liczby[c,-1]:=2;

end;

else

begin

an:=liczby[1,liczby[a,-1]-1];

if an<10 then i:=i+1;

else if an<100 then i:=i+2;

else if an<1000 then i:=i+3;

else i:=i+4;

i:=i/2+1;

i1:=11; i2:=12;

na_tablice(1,i1);

while i>0 do

begin

razy10(i1,i2);

i1:=i2; if i1=11 then i2:=12; else i2:=11;

i:=i-1;

end;

razy10(i1,c);

end;    

end;

//----------------------------------

// funkcja przygotowująca do obliczeń (serwer)

function rozdziel()

local i1;

local i2;

local k;

begin

blockread(liczba,liczby[0],34);

ogranicz(0,1);

podziel1(1,proc_number,2);

i1:=3; i2:=4;

na_tablice(3,i1);

blockwrite(liczby[i1],zakresy[0],34);

for k:=1 to proc_number-1 do

begin

dodaj(i1,2,i2);

i1:=i2; if i1=11 then i2:=12; else i2:=11;

if liczby[i1,0]%2=0 then 

begin 

dodaj1(i1,1,0,i2); 

i1:=i2; if i1=11 then i2:=12; else i2:=11;

end;

blockwrite(liczby[i1],zakresy[k],34);

end;

blockwrite(liczby[1],zakresy[proc_number],34);

// jeszcze wyzerowanie tablicy wyników

na_tablice(0,5);

for k:=0 to 31 do blockwrite(liczby[5],wyniki[k],34);

end;

//----------------------------------

// część główna programu

begin

if proc_number>64 then proc_number:=64;

if proc_number=0 then exit;

if liczba[0]%2=0 then

begin

na_tablice(2,0);

blockwrite(liczby[0],wyniki[0],34);

exit;

end;

rozdziel();

for proc:=0 to proc_number-1 pardo przygotuj();

end.