Algorytmy i Struktury Danych - Czynniki pierwsze

SPIS TREŚCI

Podrozdziały

Rozwiązanie 1
Rozwiązanie 2

Problem

Należy znaleźć rozkład liczby naturalnej p > 1 na iloczyn czynników pierwszych.

Postawiony problem posiada bardzo duże znaczenie w wielu dziedzinach informatyki – szczególnie w kryptografii. Na dzień dzisiejszy nie istnieje powszechnie znany żaden szybki algorytm rozkładu dużej liczby naturalnej na czynniki pierwsze (ang. prime factorization). Na tym fakcie opierają swoje bezpieczeństwo współczesne systemy szyfrowania informacji – np. RSA. Dla przykładu rozkład 200 cyfrowej liczby zajął 18 miesięcy wielu komputerom pracującym w sieci – w sumie czas obliczeń dla pojedynczej maszyny wyniósł ponad pół wieku!

Zasadnicze twierdzenie arytmetyki (ang. fundamental theorem of arithmetic) mówi, iż każda liczba naturalna większa od 1 może być jednoznacznie zapisana jako iloczyn liczb pierwszych. Na przykład:

1200 = 2⁴ × 3 × 5²

i nie istnieje żaden inny rozkład dla liczby 1200.

Znając rozkład liczby na czynniki pierwsze można dla niej określić wszystkie możliwe podzielniki. Na przykład każdy podzielnik liczby 1200 da się zapisać jako:

p₁₂₀₀ = 2^a × 3^b × 5^c
gdzie
a ∈ {0, 1, 2, 3, 4}
b ∈ {0, 1},
c ∈ {0, 1, 2}

Zatem wszystkich możliwych podzielników jest tyle ile wynosi iloczyn liczebności możliwych wartości a, b i c:

5 × 2 × 3 = 30

Podstawowe twierdzenie arytmetyki mówi nam, iż rozkład na czynniki pierwsze jest zawsze możliwy i jednoznaczny, lecz nie mówi, jak tego mamy dokonać.

Pierwsze podejście do znalezienia rozkładu liczby p na jej czynniki pierwsze jest bardzo prymitywne, chociaż daje oczywiście poprawny wynik. Nazywa się ono bezpośrednim poszukiwaniem rozkładu na czynniki pierwsze (ang. direct search factorization lub trial division) Będziemy sprawdzać podzielność liczby p przez kolejne liczby naturalne od 2 do pierwiastka z p. Jeśli liczba p będzie podzielna przez daną liczbę, to liczbę wyprowadzimy na wyjście, a za nowe p przyjmiemy wynik dzielenia i próbę dzielenia będziemy powtarzać dotąd, aż nie będzie to już możliwe. Wtedy przejdziemy do następnego dzielnika.

Przykład:

Rozłożyć liczbę 44100 na czynniki pierwsze.

Podział	Reszta	Czynnik	Znalezione czynniki	Uwagi
44100 : 2 = 22050	0	2	2	dzieli się
22050 : 2 = 11025	0	2	2 2	dzieli się
11025 : 2 = 5512	1	X	2 2	nie dzieli się
11025 : 3 = 3675	0	3	2 2 3	dzieli się
3675 : 3 = 1225	0	3	2 2 3 3	dzieli się
1225 : 3 = 408	1	X	2 2 3 3	nie dzieli się
1225 : 4 = 306	1	X	2 2 3 3	nie dzieli się
1225 : 5 = 245	0	5	2 2 3 3 5	dzieli się
245 : 5 = 49	0	5	2 2 3 3 5 5	dzieli się
49 : 5 = 9	4	X	2 2 3 3 5 5	nie dzieli się
49 : 6 = 8	1	X	2 2 3 3 5 5	nie dzieli się
49 : 7 = 7	0	7	2 2 3 3 5 5 7	dzieli się
7 : 7 = 1	0	7	2 2 3 3 5 5 7 7	dzieli się
Kończymy, ponieważ wynik ostatniego dzielenia jest równy 1

44100 = 2 × 2 × 3 × 3 × 5 × 5 × 7 × 7

Algorytm rozkładu liczby naturalnej na czynniki pierwsze

Wejście:

p : liczba rozkładana na czynniki pierwsze, p ∈ N, p > 1.

Wyjście:

Czynniki pierwsze liczby p.

Zmienne pomocnicze:

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

Lista kroków:

K01: g ← [sqr(p)]          ; granica sprawdzania czynników pierwszych
K02: Dla i = 2, 3, …, g:   ; w pętli sprawdzamy podzielność liczby p
     wykonuj kroki K03…K06 ; przez kolejne liczby
K03:   Dopóki p mod i = 0, ; dopóki dzielnik dzieli p
       wykonuj kroki K4…K6
K04:   Pisz i              ; wyprowadzamy go i
K05:   p ← p div i         ; dzielimy p przez i
K06:   Jeśli p = 1,        ; pętlę przerywamy, gdy stwierdzimy brak
       to zakończ          ; dalszych dzielników
K07: Jeśli p > 1,          ; p może posiadać ostatni czynnik większy
     to pisz p             ; od pierwiastka z p
K08: 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ę p i w następnym wierszu wypisuje kolejne czynniki pierwsze tej liczby.

Pascal

// Rozkład na czynniki pierwsze
// Data   : 21.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var p, i, g : longword;

begin
  readln(p);
  g := round (sqrt (p));
  for i := 2 to g do
  begin
    while p mod i = 0 do
    begin
      write (i, ' ');
      p := p div i;
    end;
    if p = 1 then break;
  end;
  if p > 1 then write (p);
  writeln;
end.

C++

// Rozkład na czynniki pierwsze
// Data   : 21.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  unsigned int p, i, g;

  cin >> p;
  g = (unsigned int)sqrt (p);
  for(i = 2; i <= g; i++)
  {
    while(! (p % i))
    {
      cout << i << " ";
      p /= i;
    }
    if(p == 1) break;
  }
  if(p > 1) cout << p;
  cout << endl;
  return 0;
}

Basic

' Rozkład na czynniki pierwsze
' Data   : 21.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger p, i, g

Input p
g = Cuint (Sqr (p))
For i = 2 To g
  While p Mod i = 0
    Print i;" ";
    p \= i
  Wend
  If p = 1 Then Exit For
Next
If p > 1 Then Print p;
Print
End

Python (dodatek)

# Rozkład na czynniki pierwsze
# Data   : 12.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import math

p = int(input())
g = int(math.sqrt(p))
for i in range(2, g + 1):
    while not(p % i):
        print(i, end=" ")
        p //= i
    if p == 1: break
if p > 1: print(p, end=" ")
print()

Wynik:

3971235724
2 2 431 2303501

Na początek: podrozdziału strony

Poprzedni algorytm sprawdza podzielność liczby p przez wszystkie kolejne liczby naturalne, zawarte w przedziale <2, sqr (p)>. Tymczasem poszukiwane podzielniki muszą być liczbami pierwszymi. Jeśli nie mamy liczb pierwszych pod ręką, to przynajmniej możemy ograniczyć dzielenia do liczb 2, 3 oraz 6k±1, dla k = 1, 2… wpadających w przedział <2, sqr (p)>. Prezentowany poniżej algorytm dokonuje takiej właśnie optymalizacji, redukując do ¹/₃ liczbę sprawdzanych podzielników.

Algorytm rozkładu liczby naturalnej na czynniki pierwsze

Wejście:

p : liczba rozkładana na czynniki pierwsze, p ∈ N, p > 1.

Wyjście:

Czynniki pierwsze liczby p.

Zmienne pomocnicze:

g : granica sprawdzania podzielności liczby p. g ∈ N,
i : kolejne podzielniki, i ∈ N.
k, d : zmienne do generacji liczb postaci 6k±1, k ∈ N, d ∈ {-1, 1}.

Lista kroków:

K01: g ← [sqr (p)]    ; wyznaczamy granicę sprawdzania podzielności
K02: k ←  1           ; współczynniki do generacji liczb postaci 6k±1
     d ← -1
K03: i ←  2           ; początek sprawdzania podzielności
K04: Dopóki i ≤ g:
     wykonuj kroki K05…K12
K05:   Dopóki p mod i = 0: ; wyznaczamy dzielnik p
       wykonuj kroki K06…K07
K06:     Pisz i       ; wypisujemy dzielnik
K07:     p ← p div i  ; modyfikujemy p
K08:   Jeśli p = 1,   ; p nie jest już podzielne
       to idź do kroku K14
K09:   Jeśli i ≥ 3,   ; wyznaczamy następny podzielnik
       to idź do kroku K11
K10:   i ← i + 1      ; podzielniki 2 i 3
       i następny obieg pętli K04
K11:   i ← 6k + d     ; pozostałe, postaci 6k ± 1
K12:   Jeśli d = 1, to:
         d ← -1       ; modyfikujemy współczynniki
         k ← k + 1    ; dla następnego podzielnika
       inaczej d ← 1
K13: Jeśli p ≠ 1,     ; ewentualny, ostatni podzielnik
     to pisz p
K14: 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ę p i w następnym wierszu wypisuje kolejne czynniki pierwsze tej liczby.

Pascal

// Rozkład na czynniki pierwsze
// Data   : 24.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var p, i, g, k : longword;
    d          : integer;
begin
  readln(p);
  g := round(sqrt(p));
  i := 2; k := 1; d := -1;

  while i <= g do
  begin
    while p mod i = 0 do
    begin
      write(i, ' ');
      p := p div i;
    end;
    if p = 1 then break;
    if i < 3 then inc(i)
    else
    begin
      i := 6 * k + d;
      if d = 1 then
      begin
        d := -1; inc(k);
      end
      else d := 1;
    end;
  end;
  if p > 1 then write(p);
  writeln;
end.

C++

// Rozkład na czynniki pierwsze
// Data   : 24.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  unsigned int p, i, g, k;
  int d;

  cin >> p;
  g = (unsigned int)sqrt(p);
  i = 2; k = 1; d = -1;

  while(i <= g)
  {
    while(! (p % i))
    {
      cout << i << " ";
      p /= i;
    }
    if(p == 1) break;
    if(i < 3) i++;
    else
    {
      i = 6 * k + d;
      if(d == 1)
      {
        d = -1; k++;
      }
      else d = 1;
    }
  }
  if(p > 1) cout << p;
  cout << endl;
  return 0;
}

Basic

' Rozkład na czynniki pierwsze
' Data   : 24.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger p, i, g, k
Dim As Integer d

Input p
g = Cuint (Sqr (p))
i = 2: k = 1: d = -1
While i <= g
  While p Mod i = 0
    Print i;" ";
    p = p \ i
  Wend
  If p = 1 Then Exit While
  If i < 3 Then
    i += 1
  Else
    i = 6 * k + d
    If d = 1 Then
      d = -1: k += 1
    Else
      d = 1
    End If
  End If
Wend
If p > 1 Then Print p;
Print
End

Python (dodatek)

# Rozkład na czynniki pierwsze
# Data   : 12.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import math

p = int(input())
g = int(math.sqrt(p))
i, k, d = 2, 1, -1
while i <= g:
    while not (p % i):
        print(i, end=" ")
        p //= i
    if p == 1: break
    if i < 3:
        i += 1
    else:
        i = 6 * k + d
        if d == 1:
            d = -1
            k += 1
        else:
            d = 1
if p > 1: print(p, end="")
print()

Wynik:

3971235724
2 2 431 2303501

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.

Czynniki pierwsze – metoda próbnych dzieleń

Problem

Rozwiązanie 1

Algorytm rozkładu liczby naturalnej na czynniki pierwsze

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 2

Algorytm rozkładu liczby naturalnej na czynniki pierwsze

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy