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

©2026 mgr Jerzy Wałaszek

Liczby pierwsze – generacja przez sprawdzanie podzielności

SPIS TREŚCI
Podrozdziały

Problem

Należy znaleźć n kolejnych liczb pierwszych (ang. primes).

Liczba naturalna p jest liczbą pierwszą (ang. prime number) posiadającą dokładnie dwa różne podzielniki: 1 i siebie samą.
W informatyce liczby pierwsze posiadają olbrzymie zastosowanie – np. w  kryptografii, czyli przy szyfrowaniu i rozszyfrowywaniu informacji. Jak jest to ważne dla handlu i bankowości w sieci, chyba nie trzeba nikogo przekonywać. Dlatego znajomość sposobów generacji liczb pierwszych jest obowiązkowa dla każdego informatyka.

Rozwiązanie 1

Pierwsze, narzucające się podejście do problemu generacji liczb pierwszych jest bardzo prymitywne. Po prostu bierzemy kolejne liczby naturalne poczynając od 2 (1 nie jest pierwsze ponieważ dzieli się tylko przez 1 i brakuje nam drugiego podzielnika). Wybraną liczbę naturalną p próbujemy dzielić przez liczby od 2 do  p-1. Jeśli żadna z  tych liczb nie jest podzielnikiem p, to  liczba p jest pierwsza. Wyprowadzamy ją i w specjalnym liczniku odnotowujemy ten fakt. Gdy licznik osiągnie stan n, kończymy algorytm.

Algorytm wyznaczania liczb pierwszych przez sprawdzanie podzielności

Wejście:

n : liczba określająca ile liczb pierwszych należy wygenerować; n ∈ N.

Wyjście:

n kolejnych liczb pierwszych.

Elementy pomocnicze:

lp : zlicza kolejno wygenerowane liczby pierwsze; lp ∈ N.
p : kolejno testowane liczby naturalne; p ∈ N.
d : kolejne dzielniki; d ∈ N.

Lista kroków:

K01: lp ← 0 ; zerujemy licznik liczb pierwszych
K02: p ← 2 ; generację rozpoczynamy od 2
K03: Dopóki lp < n: ; pętla generacji liczb pierwszych
     wykonuj kroki K04…K08
K04:   Dla d = 2, 3, …, p-1: ; pętla sprawdzania podzielności
       wykonuj krok K05 ; p przez d
K05:     Jeśli p mod d = 0,  ; jeśli p dzieli się przez d, 
         idź do kroku K08 ; to nie jest pierwsze
K06:   Pisz p ; p jest pierwsze
K07:   lp ← lp+1 ; zwiększamy licznik wygenerowanych
                 ; liczb pierwszych
K08:   p ← p+1 ; przechodzimy do kolejnej liczby, kandydata
K09: 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 w pierwszym wierszu czyta liczbę n i w następnych wierszach wypisuje n kolejnych liczb pierwszych.
Pascal
// Liczby pierwsze
// Data: 15.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var n, lp, p, d : longword;
    t : boolean;
begin
  readln(n);
  lp := 0;
  p  := 2;
  while lp < n do
  begin
    t := true;
    for d := 2 to p-1 do
      if p mod d = 0 then
      begin
        t := false;
        break;
      end;
    if t then
    begin
      write(p, ' ');
      inc(lp);
    end;
    inc(p);
  end;
  writeln;
end.
C++
// Liczby pierwsze
// Data: 15.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int n, lp, p, d;
  bool t;

  cin >> n;
  lp = 0;
  p  = 2;
  while(lp < n)
  {
    t = true;
    for(d = 2; d < p; d++)
      if(p % d == 0)
      {
        t = false;
        break;
      }
    if(t)
    {
      cout << p << " ";
      lp++;
    }
    p++;
  }
  cout << endl;
  return 0;
}
Basic
' Liczby pierwsze
' Data: 15.03.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim As Uinteger n, lp, p, d, t

Input n
lp = 0
p  = 2
While lp < n
  t = 1
  For d = 2 To p-1
    If p Mod d = 0 Then
      t = 0
      Exit For
    End If
  Next
  If t = 1 Then
    Print p;" ";
    lp += 1
  End If
  p += 1
Wend
Print
End
Python (dodatek)
# Liczby pierwsze
# Data: 6.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

n = int(input())
lp = 0
p = 2
while lp < n:
    t = True
    for d in range(2, p):
        if p%d == 0:
            t = False
            break
    if t:
        print(p, end=" ")
        lp += 1
    p += 1
print()
Wynik: 
20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

do podrozdziału  do strony 

Rozwiązanie 2

Pierwszy algorytm generowania liczb pierwszych jest bardzo nieefektywny dla dużych n. Początkowo działa szybko, później wyraźnie zwalnia, aby na  końcu osiągnąć wręcz żółwie tempo pracy. Jest to typowa cecha algorytmów o  klasie złożoności obliczeniowej O(n2) – aby przekonać się, iż liczba p jest liczbą pierwszą, algorytm musi wykonać p-2 testy. Zastanówmy się nad tym, czy algorytm faktycznie powinien sprawdzać podzielność liczby p w całym przedziale <2, p-1>.

Jeśli liczba p jest złożona, to rozkłada się na iloczyn czynników pierwszych:

p = d1×d2×…×dk

Czynników tych musi być przynajmniej 2 i muszą one być różne od 1 i p (dlaczego?). Prosta analiza pokazuje nam, iż w przedziale od pierwiastka z p do p - 1 może leżeć co najwyżej jeden czynnik. Gdyby było ich więcej, to ich iloczyn przekroczyłby wartość liczby p. Skoro drugi czynnik nie może być większy od pierwiastka z p, to musi być od niego mniejszy lub równy. Z kolei przy teście na pierwszość liczby p wystarczy nam, iż znajdziemy pierwszą podzielność, aby wyeliminować p. Wynika z tego prosty wniosek – podzielność liczby p wystarczy sprawdzić dla dzielników z przedziału od 2 do pierwiastka całkowitego z  p. Jeśli żaden podzielnik z tego przedziału nie dzieli p, to  p jest pierwsze, ponieważ w pozostałej części przedziału <2,  p-1> nie mogą już wystąpić czynniki p.

Drugie ulepszenie będzie polegało na eliminacji niektórych wartości p. Na przykład jedyną liczbą pierwszą parzystą jest 2. Wszystkie inne są już nieparzyste. Możemy pójść dalej tym tropem i dokonać dalszych eliminacji. Dwoma początkowymi liczbami pierwszymi są liczby 2 i 3. Zatem z ciągu dalszych kandydatów na liczby pierwsze możemy wyeliminować wszystkie wielokrotności liczb 2 i 3, takie jak 6,  8,  9,  10,  12,  14,  15… Liczby te mają postać 6k, 6k±2 i 6k±3, dla k = 1, 2, …. Pozostają jedynie do  sprawdzenia liczby postaci 6k±1, a tych jest już zdecydowanie mniej.

Trzecie ulepszenie polega na tym, iż sprawdzamy podzielność nie przez kolejne liczby z przedziału od 2 do pierwiastka z p lecz przez liczby pierwsze wpadające w ten przedział. Po prostu algorytm w miarę znajdowania kolejnych liczb pierwszych umieszcza je w osobnej tablicy i wykorzystuje do  testowania podzielności nowych kandydatów na liczbę pierwszą. Wymaga to co prawda tablicy n elementowej, ale opłaci się szybkością eliminacji liczb złożonych. Zwykle tak jest, iż szybkość pracy algorytmu zwiększa się kosztem większego zapotrzebowania na pamięć.

Algorytm wyznaczania liczb pierwszych przez sprawdzanie podzielności – wersja ulepszona

Wejście:

n : liczba określająca ile liczb pierwszych należy wygenerować; n ∈ N.

Wyjście:

n kolejnych liczb pierwszych. Wygenerowane liczby pierwsze znajdują się również w kolejnych n elementach tablicy tlp. Indeksy rozpoczynają się od 0.

Elementy pomocnicze:

Lp : zlicza kolejno wygenerowane liczby pierwsze; Lp ∈ N.
p : kolejno testowane liczby naturalne; p ∈  N.
g : zawiera pierwiastek całkowity z p; g ∈ N.
k : używane do generacji liczb p; k ∈ N.
d : wraz z k używane do generacji liczb p; d ∈  N.
tlp : tablica liczb pierwszych; tlp[i] ∈  N, dla i = 0, 1, …, n-1.
i : wykorzystywane przy numeracji podzielników z tlp; i ∈ N.
sqr(x) : pierwiastek kwadratowy z x.

Lista kroków:

K01: Lp ← 0 ; ustawiamy licznik liczb pierwszych
K02: k ← 1  ; oraz zmienne do generacji p = 6k±1
     d ← 1
     p ← 2
K03: Dopóki Lp < n, ; w pętli znajdujemy kolejne liczby pierwsze
     wykonuj kroki K04…K16
K04:   Jeśli Lp < 3, ; początkowe trzy liczby pierwsze są zadane z góry
       to p ← p+Lp
       i idź do kroku K14
K05:   p ← 6×k+d ; pozostałe musimy szukać wśród liczb 6k±1
K06:   Jeśli d = 1, ; modyfikujemy d i k dla następnej liczby p
       to idź do kroku K08
K07:   d ← 1
       i idź do kroku K09
K08:   d ← -1
       k ← k+1
K09:   g ← [sqr(p)] ; granica sprawdzania podzielności p
K10:   i ← 2
K11:   Dopóki tlp[i] ≤ g:
       wykonuj kroki K12…K13
K12:     Jeśli p mod tlp[i] = 0, ; sprawdzamy podzielność p
         to następny obieg pętli K03 ; przez podzielniki z tlp
K13:     i ← i+1 ; indeks następnego podzielnika
K14    tlp[Lp] ← p ; liczbę pierwszą zapamiętujemy w tlp
K15:   Pisz p
K16:   Lp ← Lp+1
K17: 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 w pierwszym wierszu czyta liczbę n i w następnych wierszach wypisuje kolejne liczby pierwsze.
Pascal
// Liczby pierwsze
// Data: 15.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

type
  Tlwarray = array of longword;

var i, k, g, n, Lp, p : longword;
    d   : integer;
    t   : boolean;
    tlp : Tlwarray;

begin
  readln(n);
  setlength(tlp, n);
  Lp := 0;
  k  := 1;
  d  := 1;
  p  := 2;
  while Lp < n do
  begin
    t := true;
    if Lp < 3 then
      inc(p, Lp)
    else
    begin
      p := 6*k+d;
      if d = 1 then
      begin
        d := -1; inc(k)
      end
      else d := 1;
      g := round(sqrt(p));
      i := 2;
      while tlp[i] <= g do
      begin
        if p mod tlp[i] = 0 then
        begin
          t := false;
          break
        end;
        inc(i)
      end
    end;
    if t then
    begin
      tlp[Lp] := p;
      write(p, ' ');
      inc(Lp)
    end
  end;
  writeln;
  SetLength(tlp, 0);
end.
C++
// Liczby pierwsze
// Data: 15.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  unsigned int i, k, g, n, Lp, p, *tlp;
  int d;
  bool t;

  cin >> n;
  tlp = new unsigned int [n];
  Lp = 0; k = 1; d = 1; p = 2;
  while(Lp < n)
  {
    t = true;
    if(Lp < 3) p += Lp;
    else
    {
      p = 6*k+d;
      if(d == 1)
      {
        d = -1; k++;
      }
      else d = 1;
      g = (unsigned int)sqrt(p);
      for(i = 2; tlp[i] <= g; i++)
        if(!(p % tlp[i]))
        {
          t = false;
          break;
        }
    }
    if(t)
    {
      tlp[Lp++] = p;
      cout << p << " ";
    }
  }
  cout << endl;
  delete [] tlp;
  return 0;
}
Basic
' Liczby pierwsze
' Data: 15.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger i, k, g, n, Lp, p, t
Dim As Integer d
 
Input n

Dim As Uinteger tlp(n)

Lp = 0: k = 1: d = 1: p = 2
While Lp < n
  t = 1
  If Lp < 3 Then
    p += Lp
  Else
    p = 6*k+d
    If d = 1 Then
      d = -1: k += 1
    Else
      d = 1
    End If
    g = Cuint(Sqr(p))
    i = 2
    While tlp(i) <= g
      If p Mod tlp(i) = 0 Then
        t = 0: Exit While
      End If 
      i += 1
    Wend
  End If
  If t = 1 Then
    tlp(Lp) = p
    Print p;" ";
    Lp += 1
  End If
Wend
Print
End
Python (dodatek)
# Liczby pierwsze
# Data: 6.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import math

n = int(input())
tlp = []
lp, k, d, p = 0, 1, 1, 2
while lp < n:
    t = True
    if lp < 3:
        p += p
    else:
        p = 6*k+d
        if d == 1:
            d = -1
            k += 1
        else:
            d = 1
        g = int(math.sqrt(p))
        i = 2
        while tlp[i] <= g:
            if p % tlp[i] == 0:
                t = False
                break
            i += 1
    if t:
        tlp.append(p)
        print(p, end=" ")
        lp += 1
print()

Generacja liczb pierwszych
(C)2020 mgr Jerzy Wałaszek

n =

…


do podrozdziału  do strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 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.