: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > działania na liczbach >

C Z Y   D A N A   L I C Z B A   J E S T   P I E R W S Z A ?

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

W przypadku sprawdzania czy liczba naturalna jest pierwsza pętle For można zastąpić pętlą While lub Repeat i wykonywać iteracje do pierwszego znalezionego dzielnika:

Function Pierwsza(N : LongInt) : Boolean;
Var
  I : LongInt;
Begin
  If N<=1 Then Pierwsza:=False
  Else
    Begin
      I:=2;
      While (N Mod I)<>0 Do Inc(I);
      Pierwsza:=(I=N);
    End;
End;

Jeśli liczna N jest liczbą pierwszą, to obie funkcje wykonywać się będą mniej więcej w tym samym czasie, gdy liczba N posiada dzielniki funkcja Pierwsza zwróci wartość False znacznie szybciej niż wyznaczenie ilości dzielników funkcją IleD (funkcja pochodzi z algorytmu o dzielnikach liczby naturalnej).

Nie jest to funkcja doskonała. Łatwo zauważyć można, że jeśli liczba naturalna N jest podzielna przez 2, to N=2*(N Div 2), czyli posiada również dzielnik równy N Div 2. W przypadku przeciwnym, tj. gdy N nie jest podzielne przez 2 nie może również być podzielne przez N Div 2. Ale nie koniec na tym, ponieważ jeśli istnieje dzielnik K większy niż N/2, to N=P*K i obie wartości P i K są całkowite. Z równości N=2*(N/2)=P*K wynika, że P=1 (K>N/2, więc P musi być mniejsze od 2). Równość ta oznacza, że K=N.
Jeśli zatem liczba całkowita nie dzieli się przez 2, to największy właściwy dzielnik nie przekracza połowy N czyli N Div 2. Obserwacja ta pozwala w powyższym przykładzie zmienić warunek logiczny i przypisanie wartości funkcji na:

While (I<=(N Div 2)) And ((N Mod I)<>0) Do Inc(I);
Pierwsza:=I>(N Div 2);

Rozumowanie powyższe można teraz powtórzyć dla dzielnika 3, 4, itd. Ogólnie: jeżeli liczba N nie jest podzielna przez I, to poszukiwanie dzielnika można ograniczyć do maksymalniej wartości N Div I:

While (I<=(N Div I)) And ((N Mod I)<>0) Do Inc(I);
Pierwsza:=I>(N Div I);

Dla N=101 pętla wykona się zaledwie dziewięć razy: 101 Div 2=51, 101 Div 3=33, 101 Div 4=25, 101 Div 5=20, 101 Div 6=15, 101 Div 7=14, 101 Div 8=12, 101 Div 9=11, 101 Div 10=10, dla I=11 warunek logiczny będzie fałszywy.
Dla liczby pierwszej N=1000003 pętla zostanie wykonana 999 razy, co daje około 1000 krotny zysk na ilości iteracji.

"Prawie" równość liczb 999 i 1000 nie jest przypadkowa. Pętla While wykonuje się dopóki I<=N Div I. Zastępując dzielenie całkowite zwykłym i mnożąc nierówność przez I otrzymamy I2<=N, z czego wynika, że dzielnika należy szukać do pierwiastka z liczby N.
Tak więc wprowadzając dodatkową zmienną P:Word można by zawartość bloku w funkcji Pierwsza zapisać następująco:

I:=2;
P:=Round(Sqrt(N));
While (I<P) And ((N Mod I)<>0) Do Inc(I);
Pierwsza:=((N Mod I)<>0);

Typ Word jest tutaj wystarczający - część całkowita z pierwiasta każdej liczby typu LongInt nie przekracza maksymalnej liczby 16-sto bitowej.