Poznasz tu definicję liczby pseudo-pierwszej i dwie wersje algorytmu sprawdzającego. Nie dowiesz się jeszcze jak wielkie znaczenie mają, ale już możesz przyjąć do wiadomości, że ja uważam, że mają I poznasz przykład programy szybko wyznaczającego liczby pierwsze w dowolnym zakresie x do y albo większej czy mniejszej niż x, bez wymagania olbrzymich zasobów pamięciowych.

Liczba pierwsza, to taka, które dzieli się tylko ze sobą i z jedynką! Czyli taka "liczbowa egoistka"

Pozostałe liczby nazywamy złożonymi.

Liczby pierwsze i pseudo-pierwsze stanowią 1/3 wszystkich liczb i znajdujemy je za pomocą 1 z 3 prostych testów:

test α (alfa)

dla x > 1
jeżeli (x mod 2 > 0) i (x mod 3 > 0) to:
wykluczamy 66(6)% liczb i na 100% x jest liczbą pierwsza albo pseudo-pierwszą;

test β (beta)

dla x > 6
jeżeli (x - 1) mod 6 = 0 lub (x - 5) mod 6) = 0 to:
wykluczamy 66(6)% liczb i na 100% x jest liczbą pierwsza albo pseudo-pierwszą.

test ω (omega)

dla x >6 (formalnie x >=5, ale... oj tam... )
jeżeli (x + 1) mod 6 = 0 lub (x + 5) mod 6) = 0 to:
wykluczamy 66(6)% liczb i na 100% x jest liczbą pierwsza albo pseudo-pierwszą.

Czym się właściwie różnią te testy? Pierwszy jest jakby oczywisty, bo jeżeli liczba nie da się podzielić przez 2 ani 3, to może być niepodzielna, ale sprawdzone muszą być oba dzielenia. W drugim i trzecim przypadku wystarczy, że pierwszy warunek będzie prawdziwy, to drugi nie musi być sprawdzany. Oczywiście oba warunki nigdy nie będą spełnione, ale zastosowanie alternatywy wykluczającej (albo) spowodowałoby konieczność sprawdzenia obu warunków. A czym się różni beta od omega!? Łatwiej sobie dodawać niż ujmować... co zwykle nie tyczy się kilogramów, ale prawie zawsze tyczy się "ego"...

Algorytmy te nazwałem odpowiednio: test666α, test666β i test666ω, bo „test 66,(6)%” byłoby zbyt skomplikowane do wymawiania.

Zatem definicje (bo mogą być dwie):

1. Liczba pseudo-pierwsza, to taka liczba, która przechodzi dowolny test666, ale nie jest liczbą pierwszą.

2. Liczba pseudo-pierwsza, to taka liczba, która przechodzi dowolny test666, ale jest liczbą złożoną.

 

Uwaga! Liczb pseudo-pierwszych nie należy mylić z pseudopierwszymi (pisanymi bez myślnika), a definicji i algorytmów podanych w tym artykule z "matematycznym voodoo", jakim są probabilistyczne testy pierwszości. Tam wiesz, że liczba jest pierwsza... no chyba, że... nie jest  Tu masz 100% pewności

Liczby pseudo-pierwsze z zakresu 1...305:

1, 25, 35, 49, 55, 65, 77, 85, 91, 95, 115, 119, 121, 125, 133, 143, 145, 155, 161, 169, 175, 185, 187, 203, 205, 209, 215, 217, 221, 235, 245, 247, 253, 259, 265, 275, 287, 289, 295, 299, 301, 305...

Dodam, że 20% liczb pseudo-pierwszych dzieli się przez 5, więc w kolejnym kroku:

x / 5

i wykluczamy 20% liczb pseudo-pierwszych

i w tym momencie na 66,(6)% + 6,(66)% = 73,(3)% x jest liczbą pierwszą.

Jak zatem znaleźć dowolną liczbę pierwszą większą niż x bez tworzenia potężnych tablic jak w przypadku Sita Eratostenesa?

Poniżej implementacja wykorzystania testu666β w języku Object Pascal:

unit pim666;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, StdCtrls;

const
  cTooSmall = 0;
  cComposite = 1;
  cPseudoPrime = 2;
  cPrime = 3;

// Funkcja CheckDiv wykonuje dzielenie liczby przez wszystkie liczby przechodzące test666 i mniejsze od pierwiastka kwadratowego z tej liczby.
function CheckDiv(qnum: qword): integer;
// Funkcja IsPrime wykonuje test666 i jeśli pozytywny, to wywołuje funkcję CheckDiv.
function IsPrime(qnum: qword): integer;
// Funkcja CheckRange generuje liczby pierwsze z zadanego zakresu.
procedure CheckRange(qfrom, qto: qword; var m: TMemo);

implementation

function CheckDiv(qnum: qword): integer;
var
  last: ValReal;
  step: qword;
begin
  // Sprawdzenie podzielności przez 5.
  if (qnum mod 5 = 0) then
  begin
    Result := cPseudoPrime;
    exit;
  end
  else
  begin
    // Ustalenie końcowego dzielnika.
    last := sqrt(QWord(qnum));
    // Ustalenie początkowego dzielnika.
    step := 7;
    // Pętla dzielenia (krok zwiększany o 4 i 2).
    while step <= last do
    begin
      if (qnum mod step = 0) then
      begin
        Result := cPseudoPrime;
        exit;
      end;
      Inc(step, 4);
      if (qnum mod step = 0) then
      begin
        Result := cPseudoPrime;
        exit;
      end;
      Inc(step, 2);
    end;
    Result := cPrime;
  end;
end;

function IsPrime(qnum: qword): integer;
var
  b: boolean;
begin
  if qnum <= 6 then
    Result := cTooSmall
  else
  begin
    // Test666beta
    b := ((qnum - 1) mod 6 = 0) or ((qnum - 5) mod 6 = 0);
    // .
    if b then
      Result := CheckDiv(qnum)
    else
    begin
      Result := cComposite;
    end;
  end;
end;

procedure CheckRange(qfrom, qto: qword; var m: TMemo);
var
  qnum: qword;
begin
  qnum := qfrom;
  // Jeśli parzysta, to zwiększ o 1.
  if (qnum mod 2 = 0) then
    Inc(qnum);
  // Ustalenie punktu startowego.
  // Jeśli liczba przechodzi test666, to sprawdzamy o 4 większą.
  // Jeśli też przechodzi test666, to sprawdzamy ją funkcją CheckDiv
  // i jeśli pierwsza, to zapis do memo, dodajemy 4
  // i przechodzimy do działania w pętli.
  // Jeśli nie przechodzi test666, to zwiększamy ją o 2 i
  // przechodzimy do działania w pętli.
  if (IsPrime(qnum) >= cPseudoPrime) then
  begin
    if (IsPrime(qnum + 4) >= cPseudoPrime) then
    begin
      if CheckDiv(qnum) = cPrime then
        m.Lines.Add(IntToStr(qnum));
      Inc(qnum, 4);
    end;
  end
  else
    Inc(qnum, 2);
  // W pętli sprawdzamy funkcją CheckDiv liczby dodając 2, potem 4.
  // Jeśli pierwsza, to do memo.
  // Aż do osiągnięcia końca zakresu.
  repeat
    if qnum > qto then
      exit;
    if CheckDiv(qnum) = cPrime then
      m.Lines.Add(IntToStr(qnum));
    Inc(qnum, 2);
    if qnum > qto then
      exit;
    if CheckDiv(qnum) = cPrime then
      m.Lines.Add(IntToStr(qnum));
    Inc(qnum, 4);
  until qnum > qTo;
end;

end.

Kompletny projekt Lazarusa i programy skompilowane (na Ubuntu, Win32 i Win64) znajdziesz na moim chomiku.

Oczywiście powyższy program i odkrycie liczb pseudo-pierwszych, to zaledwie wstęp do 100% i szybkiego sprawdzenia czy dana liczba jest liczbą pierwszą.

Do góry