Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Pierwszość liczby naturalnej – algorytmy naiwne

SPIS TREŚCI
Podrozdziały

Problem

Należy sprawdzić, czy liczba naturalna p jest liczbą pierwszą.

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(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 

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.
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 

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 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 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}.
sqr(x) : pierwiastek 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 ig:
     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:   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 kroku 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

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")

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

p =



Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.