Pierwszość liczby naturalnej – algorytmy naiwne


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3
 

Problem

Sprawdzić, czy liczba naturalna p jest pierwsza.

 

 

Rozwiązanie 1

Liczba jest pierwsza (ang. prime), jeśli nie posiada dzielników (ang. divisors) innych poza 1 i sobą samą. Pierwsze rozwiązanie testu na pierwszość (ang. primality test) polega na próbnym dzieleniu liczby p przez liczby z przedziału od 2 do [√p] i badaniu reszty z dzielenia. Powód takiego postępowania jest prosty – jeśli liczba p posiada czynnik większy od pierwiastka z p, to drugi czynnik musi być mniejszy od pierwiastka, aby ich iloczyn był równy p. W przeciwnym razie iloczyn dwóch liczb większych od √p dawałby liczbę większą od p. Zatem wystarczy przebadać podzielność p przez liczby z przedziału <2,[√p]>, aby wykluczyć liczby złożone.

 

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście
p     liczba badana na pierwszość, p N, p > 1
Wyjście:

TAK, jeśli p jest pierwsze lub NIE w przypadku przeciwnym.

Elementy pomocnicze:
g    granica sprawdzania podzielności p. g N
i  – kolejne podzielniki liczby p, i N
Lista kroków:
K01: g ← [√p] ; wyznaczamy granicę sprawdzania podzielności p
K02: Dla i = 2,3,...,g wykonuj krok K03 ; przebiegamy przez przedział <2,[√p]>
K03:     Jeśli p mod i = 0, to pisz NIE i zakończ ; jeśli liczba z przedziału <2,[√p]> dzieli p, to p nie jest pierwsze
K04: Pisz TAK ; jeśli żadna liczba z <2,[√p]> nie dzieli p, p jest pierwsze
K05: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje w pierwszym wierszu liczbę p, a w drugim wierszu wypisuje słowo TAK, jeśli liczba p jest pierwsza lub NIE w przypadku przeciwnym. W programie zastosowano zmienne 64-bitowe, zatem zakres p jest dosyć duży. Jednakże dla wielkich liczb naturalnych test na pierwszość może zająć wiele czasu.

 

Lazarus Code::Blocks Free Basic
// Badanie pierwszości
// Data   : 3.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var g,i,p : qword;
    t : boolean;

begin
  readln(p);
  g := round(sqrt(p));
  t := true;
  i := 2;
  while i <= g do
  begin
    if p mod i = 0 then
    begin
      t := false; break;
    end;
    inc(i);
  end; 
  if t then writeln('TAK')
  else      writeln('NIE');
end.
// Badanie pierwszości
// Data   : 3.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  unsigned long long g,i,p;
  bool t;

  cin >> p;
  g = (unsigned long long)sqrt(p);
  t = true;
  for(i = 2; i <= g; i++)
  {
    if(p % i == 0)
    {
      t = false; break;
    }
  }
  if(t) cout << "TAK";
  else  cout << "NIE";
  cout << endl;
  return 0;
}
' Badanie pierwszości
' Data   : 3.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Ulongint g,i,p
Dim t As Byte

Input p
g = Culngint(Sqr(p))
t = 1
For i = 2 To g
  If p Mod i = 0 Then
    t = 0: Exit For
  End If
Next 
If t = 1 Then
  Print "TAK"
Else
  Print "NIE"
End If
End

 

Wynik
  10000000000037
TAK

100000000000031
TAK

1000000000000037
TAK

10000000000000061
TAK

100000000000000003
TAK

1000000000000000003
TAK

9223372036854775783
TAK
 

 

Rozwiązanie 2

Liczba p jest liczbą pierwszą, jeśli nie dzieli się przez żadną liczbę pierwszą z przedziału <2,[√p]>. Wszystkie liczby pierwsze z wyjątkiem 2 są liczbami nieparzystymi. Możemy zatem w poprzednim algorytmie zmniejszyć dwukrotnie liczbę potrzebnych dzieleń, jeśli liczbę p będziemy dzielić przez kolejne liczby nieparzyste z przedziału <2,[√p]>. Oczywiście najpierw należy wykonać test podzielności przez 2.

 

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście
p     liczba badana na pierwszość, p N, p > 1
Wyjście:

TAK, jeśli p jest pierwsze lub NIE w przypadku przeciwnym.

Elementy pomocnicze:
g  –  granica sprawdzania podzielności p. g N
i  – kolejne podzielniki liczby p, i N
Lista kroków:
K01 Jeśli p = 2, to idź do K08 ; liczba 2 jest pierwsza
K02: Jeśli p mod 2 = 0, to idź do K10 ; sprawdzamy podzielność przez 2
K03: g ← [√p] ; granica sprawdzania podzielności
K04: i ← 3 ; pierwszy podzielnik nieparzysty
K05: Dopóki ig, wykonuj kroki K06...K07 ; w pętli sprawdzamy podzielność przez podzielniki nieparzyste
K06:     Jeśli p mod i = 0, to idź do K10  
K07:     ii + 2 ; następny podzielnik nieparzysty
K08: Pisz "TAK" ; p nie dzieli się, zatem jest pierwsze
K09: Zakończ  
K10: Pisz "NIE" ; p jest podzielne, zatem nie jest pierwsze
K11: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje w pierwszym wierszu liczbę p, a w drugim wierszu wypisuje słowo TAK, jeśli liczba p jest pierwsza lub NIE w przypadku przeciwnym.

 

Lazarus Code::Blocks Free Basic
// Badanie pierwszości
// Data   : 3.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var g,i,p : qword;
    t : boolean;

begin
  readln(p);
  t := true;
  if p > 2 then
  begin
    if p mod 2 = 0 then t := false
    else
    begin
      g := round(sqrt(p));
      i := 3;
      while i <= g do
      begin
        if p mod i = 0 then
        begin
          t := false;
          break;
        end;
        inc(i,2); 
      end;
    end;
  end
  if t then writeln('TAK')
  else      writeln('NIE');
end.
// Badanie pierwszości
// Data   : 3.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ulong;

int main()
{
  ulong g,i,p;
  bool t = true;

  cin >> p;
  if(p > 2)
  {
    if(p % 2 == 0) t = false;
    else
    {
      g = (ulong)sqrt(p);
      for(i = 3; i <= g; i += 2)
        if(p % i == 0)
        {
          t = false;
          break;
        }
    }
  }
  cout << (t ? "TAK" : "NIE") << endl;
  return 0;
}
' Badanie pierwszości
' Data   : 3.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Ulongint g,i,p
Dim t As Byte

Input p
t = 1
If p > 2 Then
  If p Mod 2 = 0 Then
    t = 0
  Else
    g = Culngint(Sqr(p))
    For i = 3 To g Step 2
      If p Mod i = 0 Then
        t = 0
        Exit For
      End If
    Next
  End If
End If
If t = 1 Then
  Print "TAK"
Else
  Print "NIE"
End If
End

 

 

Rozwiązanie 3

Liczbę niezbędnych dzieleń można dalej ograniczyć, jeśli liczbę p będziemy dzielić przez dzielniki:

 

2, 3 oraz 6k ± 1, dla k = 1,2,..., 6k ± 1 <2,[√p]>.

 

Dwa pierwsze dzielniki są początkowymi liczbami pierwszymi. Gdy wyeliminujemy czynniki 2 i 3, pozostałe liczby pierwsze muszą przybrać postać 6k ± 1. Wyjaśnienie jest bardzo proste:

 

6k = 2 × 3 × k – liczby podzielne przez 2 i 3 nie są pierwsze
6k ± 2 = 2 × (3k ± 1) – liczby podzielne przez 2 nie są pierwsze
6k ± 3 = 3 × (2k ± 1) – liczby podzielne przez 3 nie są pierwsze
6k ± 4 = 2 × (3k ± 2) – liczby podzielne przez 2 nie są pierwsze

 

Pozostają liczby postaci:

 

6k ± 1, które mogą być pierwsze (ale nie muszą!). Jednakże liczb tych jest 1/3 w stosunku do pierwotnego algorytmu, co zaowocuje zmniejszeniem liczby wykonywanych dzieleń.

 

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście
p     liczba badana na pierwszość, p N, p > 1
Wyjście:

TAK, jeśli p jest pierwsze lub NIE w przypadku przeciwnym.

Elementy pomocnicze:
g    granica sprawdzania podzielności p. g N
i  – podzielniki liczby p, i N
k  – mnożnik do wyznaczania podzielników postaci 6k ± 1, k N
d  – zmienna pomocnicza do wyznaczania podzielników, d {false,true}
Lista kroków:
K01: g ← [√p] ; wyznaczamy granicę sprawdzania podzielności
K02: i ← 2 ; pierwszy dzielnik
K03: k ← 1;  d ← false; ; ustawiamy zmienne pomocnicze
K04: Dopóki ig, wykonuj kroki K05...K14  
K05:     Jeśli p mod i = 0, to idź do K17 ; sprawdzamy podzielność p przez i
K06:     Jeśli i > 2, to idź do K09 ; podzielniki > 3 generujemy wg wzoru 6k ± 1
K07:     ii + 1 ; podzielniki 2 i 3
K08:     Następny obieg pętli K04  
K09:     d ← ¬ d ; generujemy podzielnik i = 6k ± 1
K10:     i ← 6k  
K11:     Jeśli d = true, to idź do K14  
K12:     kk + 1  
K13     ii + 1 i następny obieg pętli K04  
K14     ii - 1  
K15: Pisz "TAK" ; p nie dzieli się przez żaden z dzielników
K16: Zakończ  
K17: Pisz "NIE" ; p nie jest pierwsze
K18: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje w pierwszym wierszu liczbę p, a w drugim wierszu wypisuje słowo TAK, jeśli liczba p jest pierwsza lub NIE w przypadku przeciwnym.

 

Lazarus Code::Blocks Free Basic
// Badanie pierwszości
// Data   : 3.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var i,g,k,p : qword;
    d,t : boolean;
begin
  readln(p);
  g := round(sqrt(p));
  i := 2;
  k := 1; d := false;
  t := true;
  while i <= g do
  begin
    if p mod i = 0 then
    begin
      t := false; break;
    end;
    if i > 2 then
    begin
      d := not d;
      i := (k shl 1) + (k shl 2);
      if d then dec(i)
      else
      begin
        inc(k); inc(i);
      end;
    end
    else inc(i);
  end;
  if t then writeln('TAK')
  else      writeln('NIE');
end.

 

// Badanie pierwszości
// Data   : 3.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ulong;

int main()
{
  ulong i,g,k,p;
  bool d,t;

  cin >> p;
  g = (ulong)sqrt(p);
  i = 2;
  k = 1; d = false;
  t = true;
  while(i <= g)
  {
    if(p % i == 0)
    {
      t = false; break;
    }
    if(i > 2)
    {
      d = !d;
      i = (k << 1) + (k << 2);
      if(d) i--;
      else
      {
        k++; i++;
      }
    }
    else i++;
  }
  cout << (t ? "TAK" : "NIE") << endl;
  return 0;
}
' Badanie pierwszości
' Data   : 3.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Ulongint i,g,k,p
Dim As Byte d,t

Input p
g = Culngint(Sqr(p))
i = 2
k = 1: d = 0
t = 1
While i <= g
  If p Mod i = 0 Then
    t = 0: Exit While
  End If
  If i > 2 Then
    d = 1 - d
    i = (k Shl 1) + (k Shl 2)
    If d = 1 Then
      i -= 1
    Else
      k += 1: i += 1
    End If
  Else
    i += 1
  End If
Wend
If t = 1 Then
  Print "TAK"
Else
  Print "NIE"
End If
End

 

Badanie pierwszości
(C)2012 mgr Jerzy Wałaszek

p =


...

 



List do administratora Serwisu Edukacyjnego I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo  , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

(C)2014 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.