Algorytmy i Struktury Danych - Pierwszość liczby naturalnej

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 ] (do części całkowitej z pierwiastka z 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,
sqr(x) : pierwiastek z x.

Lista kroków:

K01: g ← [sqr(p)] ; wyznaczamy granicę sprawdzania podzielności p
K02: Dla i = 2, 3, …, g: ; przebiegamy przez przedział <2, [√p]>
     wykonuj krok K03
K03:   Jeśli p mod i = 0, ; jeśli liczba z przedziału <2, [√p]> dzieli p, 
       to pisz NIE i zakończ ; to p nie jest pierwsze
K04: Pisz TAK ; jeśli żadna liczba z <2, [√p]> nie dzieli p, p jest pierwsze
K05: Zakończ

Przykładowe programy

Uwaga:

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.

Pascal

// Badanie pierwszości
// Data   : 3.04.2008
// (C)2020 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.

C++

// Badanie pierwszości
// Data   : 3.04.2008
// (C)2020 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;
}

Basic

' Badanie pierwszości
' Data   : 3.04.2008
' (C)2020 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

Python (dodatek)

# Badanie pierwszości
# Data   : 13.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import math

p = int(input())
g = int(math.sqrt(p))
t = True
for i in range(2, g+1):
    if not(p % i):
        t = False
        break
if t:
    print("TAK")
else:
    print("NIE")

Wynik:

10000000000037
TAK

100000000000031
TAK

1000000000000037
TAK

10000000000000061
TAK

100000000000000003
TAK

1000000000000000003
TAK

9223372036854775783
TAK

Na początek: podrozdziału strony

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.
sqr(x) : pierwiastek z x.

Lista kroków:

K01: Jeśli p = 2,       ; liczba 2 jest pierwsza
     to idź do kroku K08
K02: Jeśli p mod 2 = 0, ; sprawdzamy podzielność przez 2
     to idź do kroku K10
K03: g ← [sqr(p)]       ; granica sprawdzania podzielności
K04: i ← 3              ; pierwszy podzielnik nieparzysty
K05: Dopóki i ≤ g,      ; w pętli sprawdzamy podzielność
     wykonuj kroki K06…K07 ; przez podzielniki nieparzyste
K06:   Jeśli p mod i = 0, 
       to idź do kroku K10
K07:   i ← i+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

Przykładowe programy

Uwaga:

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.

Pascal

// Badanie pierwszości
// Data   : 3.04.2008
// (C)2020 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.

C++

// Badanie pierwszości
// Data   : 3.04.2008
// (C)2020 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;
}

Basic

' Badanie pierwszości
' Data   : 3.04.2008
' (C)2020 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

Python (dodatek)

# Badanie pierwszości
# Data   : 13.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------
import math

p = int(input())
t = True
if p > 2:
    if not (p % 2):
        t = False
    else:
        g = int(math.sqrt(p))
        for i in range(3, g+1, 2):
            if not (p % i):
                t = False
                break
if t:
    print("TAK")
else:
    print("NIE")

Na początek: podrozdziału strony

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 lub 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 ¹/₃ 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}.
sqr(x) : pierwiastek kwadratowy z x.

Lista kroków:

K01: g ← [sqr(p)] ; wyznaczamy granicę sprawdzania podzielności
K02: i ← 2 ; pierwszy dzielnik
K03: k ← 1 ; ustawiamy Elementy pomocnicze
     d ← false
K04: Dopóki i ≤ g:
     wykonuj kroki K05…K14
K05:   Jeśli p mod i = 0, ; sprawdzamy podzielność p przez i
       to idź do kroku K17
K06:   Jeśli i > 2, ; podzielniki > 3 generujemy wg wzoru 6k±1
       to idź do kroku K09
K07:   i ← i+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 kroku K14
K12:   k ← k+1
K13    i ← i+1
       i następny obieg pętli K04
K14    i ← i-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

Przykładowe programy

Uwaga:

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.

Pascal

// Badanie pierwszości
// Data   : 3.04.2008
// (C)2020 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.

C++

// Badanie pierwszości
// Data   : 3.04.2008
// (C)2020 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;
}

Basic

' Badanie pierwszości
' Data   : 3.04.2008
' (C)2020 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

Python (dodatek)

# Badanie pierwszości
# Data   : 13.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import math

p = int(input())
g = int(math.sqrt(p))
i, k, d = 2, 1, 0
t = True
while i <= g:
    if not (p % i):
        t = False
        break
    if i > 2:
        d = 1-d
        i = (k << 1)+(k << 2)
        if d:
            i -= 1
        else:
            k += 1
            i += 1
    else:
        i += 1
if t:
    print("TAK")
else:
    print("NIE")

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Pierwszość liczby naturalnej – algorytmy naiwne

Problem

Rozwiązanie 1

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 2

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 3

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy