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 \([\sqrt{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 \(\sqrt{p}\) dawałby liczbę większą od \(p\). Zatem wystarczy przebadać podzielność \(p\) przez liczby z przedziału \({[2;[\sqrt{p}]]}\), aby wykluczyć liczby złożone.

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście:

\(p\) : liczba badana na pierwszość, \({p\in\mathbb{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\in\mathbb{N}}\).
\(i\) : kolejne podzielniki liczby \(p\); \({i\in\mathbb{N}}\).

Lista kroków:

K01:	\(g\leftarrow[\sqrt{p}]\) ; wyznaczamy granicę sprawdzania podzielności \(p\)
K02:	Dla \(i=2,3,\dots,g:\) ; przebiegamy przez przedział \([2; [\sqrt{p}]]\) wykonuj krok K03
K03:	Jeśli \(p\bmod i=0,\) ; jeśli liczba z przedziału \([2; [\sqrt{p}]]\) dzieli \(p\), to pisz NIE i zakończ ; to \(p\) nie jest pierwsze
K04:	Pisz TAK ; jeśli żadna liczba z \([2; [\sqrt{p}]]\) nie dzieli \(p\), to \(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{-}\text{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

do podrozdziału do strony

Liczba \(p\) jest liczbą pierwszą, jeśli nie dzieli się przez żadną liczbę pierwszą z przedziału \({[2; [\sqrt{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; [\sqrt{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\in\mathbb{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\in\mathbb{N}}\).
\(i\) : kolejne podzielniki liczby \(p\). \({i\in\mathbb{N}}\).

Lista kroków:

K01:	Jeśli \(p=2,\) ; liczba \(2\) jest pierwsza to idź do kroku K08
K02:	Jeśli \(p\bmod2=0,\) ; sprawdzamy podzielność przez \(2\) to idź do kroku K10
K03:	\(g\leftarrow[\sqrt{p}]\) ; granica sprawdzania podzielności
K04:	\(i\leftarrow3\) ; pierwszy podzielnik nieparzysty
K05:	Dopóki \(i\le g,\) ; w pętli sprawdzamy podzielność wykonuj kroki K06…K07 ; przez podzielniki nieparzyste
K06:	Jeśli \(p\bmod i=0,\) to idź do kroku K10
K07:	\(i\leftarrow 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")

do podrozdziału do strony

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

\(2,3\) oraz \(6\cdot k\pm1\), dla \({k=1,2,\dots}\)
\(6\cdot k\pm1\in[2;[\sqrt{p}]]\).

Dwa pierwsze dzielniki są początkowymi liczbami pierwszymi. Gdy wyeliminujemy czynniki \(2\) i \(3\), pozostałe liczby pierwsze muszą przybrać postać \({6\cdot k\pm1}\). Wyjaśnienie jest bardzo proste:

\(6\cdot k=2\cdot3\cdot k\) – liczby podzielne przez \(2\) lub \(3\) nie są pierwsze
\(6\cdot k\pm2=2\cdot(3\cdot k\pm1)\) – liczby podzielne przez \(2\) nie są pierwsze
\(6\cdot k\pm3=3\cdot(2\cdot k\pm1)\) – liczby podzielne przez \(3\) nie są pierwsze
\(6\cdot k\pm4=2\cdot(3\cdot k\pm2)\) – liczby podzielne przez \(2\) nie są pierwsze

Pozostają liczby postaci:

\(6k\pm1\), które mogą być pierwsze (ale nie muszą!). Jednakże liczb tych jest \(\frac{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\in\mathbb{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\in\mathbb{N}}\).
\(i\) : podzielniki liczby \(p\); \({i\in\mathbb{N}}\).
\(k\) : mnożnik do wyznaczania podzielników postaci \({6\cdot k\pm1}\); \({k\in\mathbb{N}}\).
\(d\) : zmienna pomocnicza do wyznaczania podzielników; \({d\in\{false,true\}}\).

Lista kroków:

K01:	\(g\leftarrow[\sqrt{p}]\) ; wyznaczamy granicę sprawdzania podzielności
K02:	\(i\leftarrow2\) ; pierwszy dzielnik
K03:	\(k\leftarrow1\) ; ustawiamy elementy pomocnicze \(d\leftarrow\text{false}\)
K04:	Dopóki \(i\le g:\) wykonuj kroki K05…K14
K05:	Jeśli \(p\bmod i=0,\) ; sprawdzamy podzielność \(p\) przez \(i\) to idź do kroku K17
K06:	Jeśli \(i>2,\) ; podzielniki \(>3\) generujemy wg wzoru \(6\cdot k\pm1\) to idź do kroku K09
K07:	\(i\leftarrow i+1\) ; podzielniki \(2\) i \(3\)
K08:	Następny obieg pętli K04
K09:	\(d\leftarrow\neg d\) ; generujemy podzielnik \(i=6\cdot k\pm1\)
K10:	\(i\leftarrow6\cdot k\)
K11:	Jeśli \(d=\text{true},\) to idź do kroku K14
K12:	\(k\leftarrow k+1\)
K13:	\(i\leftarrow i+1\) i następny obieg pętli K04
K14:	\(i\leftarrow i-1\)
K15:	Pisz TAK ; \(p\) nie dzieli się przez żaden z dzielników
K16:	Zakończ
K17:	Pisz NIE ; \(p\) dzieli się, 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")

JavaScript

<html>
  <head>
    <title>
      Badanie pierwszości
    </title>
  </head>
  <body>

<div style="overflow-x: auto; overflow-y: hidden;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>
          Badanie pierwszości
          </b><br/>
          &nbsp;&nbsp;(C)2026
          mgr Jerzy Wałaszek
          &nbsp;&nbsp;<hr>
          p = <input
              type="text"
              name="inp_p"
              size="16"
              value="32767"
              style="text-align:
                     right">
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

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

function main()
{
  var i,g,k,p,d,t,s;

  p = parseInt(document.frm
      .inp_p.value);
  if(!isNaN(p))
  {
    g = Math.floor(Math.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 * 6;
        if(d) i--;
        else
        {
          k++;
          i++;
        }
      }
      else i++;
    }
    s = t ? "TAK" : "NIE";
  }
  else s = "Złe dane wejściowe!";
  document.getElementById("out")
  .innerHTML = s;
}

</script>

  </body>
</html>

do podrozdziału do strony

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