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

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

Zmienne pomocnicze:

g  –  granica sprawdzania podzielności p. g  ∈ N.
i  – kolejne podzielniki liczby p, i  ∈ N.

Lista kroków:

K01: g  ← [ sqr ( 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  

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

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

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