Rozkład na czynniki pierwsze - co to czynniki pierwsze, kalkulator oraz implementacja algorytmu | Korepetycje do matury z informatyki

27 maja 2025
Posted by: Damian
Category: Baza wiedzy

Rozkład na czynniki pierwsze okazuje się istotny nie tylko w czasie zajęć z matematyki, ale również z informatyki. Może się okazać, że jedno z zadań na maturze z informatyki będzie wymagać zastosowania rozkładu na czynniki pierwsze w ramach algorytmu. W poniższym artykule dowiesz się w jaki sposób można rozłożyć wartość na odpowiednią liczbę czynników.

Spis treści

1 Rozkład na czynniki pierwsze – Kalkulator

2 Co to czynniki pierwsze?

3 Jak rozłożyć liczby na czynniki pierwsze – opis metody

4 Przykład rozkładu liczby na czynniki pierwsze – krok po kroku

5 Rozkładanie na czynniki pierwsze – Implementacja algorytmu

5.1 Schemat blokowy i pseudokod – rozkład liczby na czynniki pierwsze

5.2 Rozkład liczby na czynniki pierwsze – Python, C++ i Java

6 Rozłóż podane liczby na czynniki pierwsze – zadania

7 QUIZ – Sprawdź swoją wiedzę

8 Najczęściej zadawane pytania o rozkład liczby na czynniki pierwsze

Rozkład na czynniki pierwsze – Kalkulator

Rozkład na czynniki pierwsze

Wynik

Komunikat:
Wynik:

Co to czynniki pierwsze?

Rozkład na czynniki pierwsze to zapisanie liczby złożonej w postaci iloczynu liczb pierwszych, a więc czynniki pierwsze to liczby pierwsze, które pomnożone ze sobą tworzą określoną wartość. Co ciekawe każdą liczbę naturalną większą od 1 można przedstawić w tej postaci np. 4 = 2 * 2, 156 = 2 * 2 * 3 * 13, 13 = 13 lub 156 = 2² * 3 * 13.

Jest to pomocne na przykład w szukaniu NWD (największego wspólnego dzielnika) czy NWW (największej wspólnej wielokrotności). Ułatwia to też sprawdzenie podzielności liczb. Wystarczy sprawdzić czy wszystkie czynniki liczby występują w rozkładzie na czynniki innej liczby – jeśli tak, mniejsza dzieli tę większą.

Przykład.

798 = 2 * 3 * 7 * 19

133 = 7 * 19

17 = 17

Wszystkie czynniki pierwsze liczby 133 są obecne w rozkładzie 798, więc 133 dzieli 798. Z kolei 17 jest liczbą pierwszą, więc nie można jej podzielić na więcej czynników pierwszych.

Jak rozłożyć liczby na czynniki pierwsze – opis metody

Poniżej opisano w jaki sposób rozłożyć podane liczby na czynniki pierwsze.

Rozkład na czynniki pierwsze GIF — Rozkład liczby na czynniki pierwsze to proces dzielenia liczby na jej najmniejsze dzielniki, które są liczbami pierwszymi.

Etap 1 – Zacznij od najmniejszej liczby pierwszej

Najmniejszą liczbą pierwszą jest 2.
Sprawdź, czy liczba, którą chcesz rozłożyć, dzieli się przez 2. Jeśli tak, zapisz 2 jako czynnik, a wynik podziel przez 2.
Przykład. 120 / 2 = 60, zapisujemy 2. Następnie 60 / 2 = 30, więc zapisujemy ponownie 2. Następnie 30 / 2 = 15, czyli zapisujemy znowu 2. Ale 15 nie dzieli się przez 2, więc przechodzimy do kolejnego kroku.

Etap 2 – Przejdź do kolejnych liczb pierwszych

Jeśli liczba nie dzieli się przez 2, spróbuj z kolejną liczbą pierwszą, czyli 3.
Kontynuuj testowanie kolejnych liczb pierwszych (2, 3, 5, 7, itd.) do momentu, aż otrzymasz 1 jako wynik dzielenia.
Przykład. 15 / 3 = 5, zapisujemy 3. Następnie wartość 5 nie dzieli się przez 3, więc próbujemy z kolejną liczbą pierwszą czyli 5. W tym przypadku 5 / 5 = 1, więc zapisujemy 5, a rozkład na czynniki pierwsze został zakończony.

Etap 3 – Powtarzaj proces

Przy każdym podziale zapisuj czynnik i aktualizuj liczbę, aż zostanie rozłożona w całości.

Przykład. 120 = 2 * 2 * 2 * 3 * 5 = 23 * 3 * 5.

Przykład rozkładu liczby na czynniki pierwsze – krok po kroku

Pod spodem znajdziesz kilka przykładów rozkładu liczb na czynniki pierwsze.

Rozkład liczby 150

Podziel przez 2:
150 / 2 = 75, zapisujemy 2.
Podziel przez 3:
75 / 3 = 25, zapisujemy 3.
Podziel przez 5:
25 / 5 = 5, zapisujemy 5.
Podziel przez 5 ponownie:
5 / 5 = 1, zapisujemy 5 i kończymy rozkład bo wynik to 1.

Rozkład: 150 = 2 * 3 * 5 * 5 = 2 * 3 * 52.

Rozkład liczby 550

550 / 2 = 275, zapisujemy 2.
275 / 5 = 55, zapisujemy 5.
55 / 5 = 11, zapisujemy 5.

11 / 11 = 1, Zapisujemy 11 i kończymy rozkład bo wynik to 1.

Rozkład: 550 = 2 * 5 * 5 * 11 = 2 * 52 * 11.

Rozkład liczby 30

30/2=1530 / 2 = 15, zapisujemy 2.

15/3=515 / 3 = 5, zapisujemy 3.
5 / 5 = 1, zapisujemy 5 i kończymy rozkład bo wynik to 1.

Rozkład: 30 = 2 * 3 * 5.

Rozkład liczby 72

72 / 2 = 36, zapisujemy 2.
36 / 2 = 18, zapisujemy 2.
18 / 2 = 9, zapisujemy 2.
9 / 3 = 3, zapisujemy 3.
3 / 3 = 1, zapisujemy 3 i kończymy rozkład bo wynik to 1.

Rozkład: 72 = 2 * 2 * 2 * 3 * 3 = 23 * 32.

Rozkład liczby 234

234 / 2 = 117, zapisujemy 2.
117 / 3 = 39, zapisujemy 3.
39 / 3 = 13, zapisujemy 3.
13 / 13 = 1, zapisujemy 13 i kończymy rozkład bo wynik to 1.

Rozkład: 234 = 2 * 3 * 3 * 13 = 2 * 32 * 13.

Rozkład liczby 1554

1554 / 2 = 777, zapisujemy 2.
777 / 3 = 259, zapisujemy 3.
259 / 7 = 37, zapisujemy 7.
37 / 37 = 1, zapisujemy 37 i kończymy rozkład bo wynik to 1.

Rozkład: 1554 = 2 * 3 * 7 * 37.

Rozkład liczby 756

756 / 2 = 378, zapisujemy 2.
378 / 2 = 189, zapisujemy 2.
189 / 3 = 63, zapisujemy 3.
63 / 3 = 21, zapisujemy 3.
21 / 3 = 7, zapisujemy 3.
7 / 7 = 1, zapisujemy 7 i kończymy rozkład bo wynik to 1.

Rozkład: 756 = 2 * 2 * 3 * 3 * 3 * 7 = 22 * 33 * 7.

Rozkładanie na czynniki pierwsze – Implementacja algorytmu

Najprostszym sposobem żeby wartość rozłożyć na czynniki pierwsze jest przejście po kolejnych liczbach zaczynając od 2, sprawdzanie czy dzieli ona sprawdzaną liczbę, a następnie dodanie jej do listy (tablicy). Jednak trzeba pamiętać, że dana liczba może być dzielnikiem kilka razy, więc trzeba użyć pętli dopóki (while) zamiast klasycznego jeżeli (if).

Jednak czy nie spowoduje to np. dodania liczby złożonej do naszej listy? Okazuje się że nie, ponieważ każda liczba złożona która pojawi się jako kandydat, nie będzie dzieliła liczby, gdyż jej czynników (które są mniejsze) nie będzie już w rozkładzie liczby.

Schemat blokowy i pseudokod – rozkład liczby na czynniki pierwsze

Rozkład na czynniki pierwsze - schemat blokowy — W przypadku powyższego schematu blokowego, zastosowano czynniki [ ] jako utworzenie pustej listy/tablicy, gdzie pierwszy element zaczyna się od 1, a nie od 0.

Implementacja w pseudokodzie:

Funkcja czynniki_pierwsze(liczba):
    czynniki ← [ ]
    dzielnik ← 2
    i ← 1
    Dopóki liczba ≠ 1 wykonuj
        Dopóki liczba mod dzielnik = 0 wykonuj
            czynniki.dodaj(dzielnik)
            liczba ← liczba div dzielnik
            i ← i + 1
        dzielnik ← dzielnik + 1
    Zwróć czynniki [ ]

Funkcja czynniki_pierwsze(liczba):

czynniki ← [ ]

dzielnik ← 2

i ← 1

Dopóki liczba ≠ 1 wykonuj

Dopóki liczba mod dzielnik = 0 wykonuj

czynniki.dodaj(dzielnik)

liczba ← liczba div dzielnik

i ← i + 1

dzielnik ← dzielnik + 1

Zwróć czynniki [ ]

Opis rozkładu na czynniki pierwsze – pseudokod

linia – Rozpoczyna definicję funkcji o nazwie czynniki_pierwsze, która przyjmuje jako argument wartość liczba.
linia – Tworzy pustą listę o nazwie czynniki, która będzie przechowywać kolejne czynniki pierwsze liczby.
linia – Inicjalizuje zmienną dzielnik wartością 2, ponieważ jest to najmniejsza liczba pierwsza, od której zaczyna się dzielenie.
linia – Inicjalizuje zmienną i jako 0. Ta zmienna będzie używana jako indeks do wstawiania kolejnych czynników do listy czynniki.
linia – Rozpoczyna pętlę, która będzie trwała, dopóki liczba nie zostanie zredukowana do 1. Oznacza to, że liczba została całkowicie rozłożona na czynniki.
linia – Rozpoczyna wewnętrzną pętlę sprawdzającą, czy liczba jest podzielna przez aktualny dzielnik. Jeśli reszta z dzielenia (mod) wynosi 0, oznacza to, że dzielnik jest czynnikiem liczby.
linia – Dodaje wartość dzielnik do listy czynniki na ostatnią pozycję. Należy pamiętać, że taka instrukcja jest niedozwolona na maturze z informatyki.
linia – Dzieli liczba przez dzielnik i aktualizuje wartość liczba. Oznacza to usunięcie czynnika dzielnik z liczby.
linia – Zwiększa wartość zmiennej i o 1, aby móc wstawić czynnik na kolejne miejsce w liście czynniki.
linia – Jeśli liczba nie jest już podzielna przez bieżący dzielnik, zwiększa dzielnik o 1, aby sprawdzić kolejną liczbę jako potencjalny czynnik.
linia – Kończy działanie funkcji i zwraca listę czynniki, która zawiera wszystkie czynniki pierwsze początkowej wartości liczba.

Uwaga: Należy pamiętać, że instrukcja czynniki.dodaj(dzielnik) jest niedozwolona na maturze. W tym przypadku jest stosowana, dla ułatwienia zrozumienia działania algorytmu.

Rozkład liczby na czynniki pierwsze – Python, C++ i Java

Rozkład na czynniki pierwsze – Python

def czynniki_pierwsze(liczba):
    czynniki = []
    dzielnik = 2
    while liczba != 1:
        while liczba % dzielnik == 0:
            czynniki.append(dzielnik)
            liczba //= dzielnik
        dzielnik += 1
    return czynniki
print(czynniki_pierwsze(120))

def czynniki_pierwsze(liczba):

czynniki = []

dzielnik = 2

while liczba != 1:

while liczba % dzielnik == 0:

czynniki.append(dzielnik)

liczba //= dzielnik

dzielnik += 1

return czynniki

print(czynniki_pierwsze(120))

Rozkład na czynniki pierwsze – C++

#include <vector>
#include <iostream>

using namespace std;

vector<int> czynniki_pierwsze(int liczba) {
    vector<int> czynniki;
    int dzielnik = 2;
    
    while (liczba != 1) {
        while (liczba % dzielnik == 0) {
            czynniki.push_back(dzielnik);
            liczba /= dzielnik;
        }
        dzielnik++;
    }
    
    return czynniki;
}

int main() {
    vector<int> czynniki = czynniki_pierwsze(120);
    for (int i = 0; i < czynniki.size(); i++) {
        cout << czynniki[i] << " ";
    }
    
    return 0;
}

#include <vector>

#include <iostream>

using namespace std;

vector<int> czynniki_pierwsze(int liczba) {

vector<int> czynniki;

int dzielnik = 2;

while (liczba != 1) {

while (liczba % dzielnik == 0) {

czynniki.push_back(dzielnik);

liczba /= dzielnik;

}

dzielnik++;

}

return czynniki;

}

int main() {

vector<int> czynniki = czynniki_pierwsze(120);

for (int i = 0; i < czynniki.size(); i++) {

cout << czynniki[i] << " ";

}

return 0;

}

Rozkład na czynniki pierwsze – Java

import java.util.ArrayList;

public class Main {
    public static ArrayList<Integer> czynnikiPierwsze(int liczba) {
        ArrayList<Integer> czynniki = new ArrayList<>();
        int dzielnik = 2; 
        while (liczba != 1) {
            while (liczba % dzielnik == 0) {
                czynniki.add(dzielnik);
                liczba /= dzielnik;
            }
            dzielnik++;
        } 
        return czynniki;
    }

    public static void main(String[] args) {
        ArrayList<Integer> czynniki = czynnikiPierwsze(120); 
        for (int i = 0; i < czynniki.size(); i++) {
            System.out.print(czynniki.get(i) + " ");
        }
    }
}

import java.util.ArrayList;

public class Main {

public static ArrayList<Integer> czynnikiPierwsze(int liczba) {

ArrayList<Integer> czynniki = new ArrayList<>();

int dzielnik = 2;

while (liczba != 1) {

while (liczba % dzielnik == 0) {

czynniki.add(dzielnik);

liczba /= dzielnik;

}

dzielnik++;

}

return czynniki;

}

public static void main(String[] args) {

ArrayList<Integer> czynniki = czynnikiPierwsze(120);

for (int i = 0; i < czynniki.size(); i++) {

System.out.print(czynniki.get(i) + " ");

}

Uwaga: Gdyby w jakimś zadaniu trzeba było działać tylko na dzielnikach bez powtórek, wystarczy użyć set.

Python:

dzielniki_unikatowe = set(dzielniki)

1	dzielniki_unikatowe = set(dzielniki)

C++:

#include <set>
using namespace std;
set<int> czynniki_unikatowe(czynniki.begin(), czynniki.end());

#include <set>

using namespace std;

set<int> czynniki_unikatowe(czynniki.begin(), czynniki.end());

Java:

import java.util.Set;
Set<Integer> set = new HashSet<>(arrayList);

1 2	import java.util.Set; Set<Integer> set = new HashSet<>(arrayList);

Rozłóż podane liczby na czynniki pierwsze – zadania

Znajdź rozkład na czynniki pierwsze podanych liczb według podanego wcześniej sposobu. Po kliknięciu w zadanie, pojawi się odpowiedź.

Zadanie 1. Rozłóż 48 na czynniki pierwsze

Odpowiedź: 48 = 2 * 2 * 2 * 2 * 3 = 2⁴ * 3

Zadanie 2. Rozłóż 120 na czynniki pierwsze

Odpowiedź: 120 = 2 * 2 * 2 * 3 * 5 = 2³ * 3 * 5

Zadanie 3. Rozłóż 210 na czynniki pierwsze

Odpowiedź: 210 = 2 * 3 * 5 * 7

Zadanie 4. Rozłóż 325 na czynniki pierwsze

Odpowiedź: 325 = 5 * 5 * 13 = 5² * 13

Zadanie 5. Rozłóż 1001 na czynniki pierwsze

Odpowiedź: 1001 = 7 * 11 * 13

QUIZ – Sprawdź swoją wiedzę

Najczęściej zadawane pytania o rozkład liczby na czynniki pierwsze

Czy każdą liczbę można rozłożyć na czynniki pierwsze?

Tak, każdą liczbę naturalną większą od 1 można rozłożyć na czynniki pierwsze. Jest to wynik Podstawowego Twierdzenia Arytmetyki, które mówi, że każda liczba naturalna większa od 1 ma dokładnie jeden rozkład na czynniki pierwsze, nie licząc kolejności czynników.

Jak najszybciej rozłożyć dużą liczbę na czynniki pierwsze?

Rozkład dużych liczb na czynniki pierwsze jest trudnym problemem, szczególnie w kryptografii. Istnieje jednak wiele algorytmów, które przyspieszają ten proces:

Algorytm próbnych podziałów (Trial Division) – polega na sprawdzaniu kolejnych liczb pierwszych jako dzielników. Jest prosty, ale bardzo wolny dla dużych liczb.

Algorytm Fermata – szuka rozkładu liczby jako różnicy dwóch kwadratów. Działa dobrze dla liczb bliskich kwadratom.

Metoda Rho Pollarda – wykorzystuje funkcję iteracyjną do wykrycia wspólnego dzielnika dwóch liczb w sposób probabilistyczny. Jest szybki dla liczb z mniejszymi czynnikami pierwszymi.

Czy istnieją liczby, które są szczególnie trudne do rozłożenia na czynniki?

Tak, istnieją liczby, które są szczególnie trudne do rozłożenia na czynniki, głównie dlatego, że składają się z dużych liczb pierwszych i są iloczynem dwóch lub więcej liczb pierwszych o podobnych rozmiarach.

Przykłady trudnych liczb:

Liczby RSA – są to liczby będące iloczynem dwóch bardzo dużych liczb pierwszych (np. po 1024 bity). Ich rozkład na czynniki stanowi podstawę bezpieczeństwa wielu systemów szyfrowania.
Liczby Fermata – niektóre z nich są bardzo trudne do rozłożenia, mimo że są stosunkowo małe.
Liczby Carmichaela – liczby pseudopierwsze, które mogą oszukiwać testy pierwszości. Są trudniejsze do analizy w niektórych algorytmach.

Rozkład na czynniki pierwsze – co to czynniki pierwsze, kalkulator oraz implementacja algorytmu

Rozkład na czynniki pierwsze – Kalkulator

Co to czynniki pierwsze?

Jak rozłożyć liczby na czynniki pierwsze – opis metody

Przykład rozkładu liczby na czynniki pierwsze – krok po kroku

Rozkładanie na czynniki pierwsze – Implementacja algorytmu

Schemat blokowy i pseudokod – rozkład liczby na czynniki pierwsze

Rozkład liczby na czynniki pierwsze – Python, C++ i Java

Rozłóż podane liczby na czynniki pierwsze – zadania

QUIZ – Sprawdź swoją wiedzę

Najczęściej zadawane pytania o rozkład liczby na czynniki pierwsze

Liczby pierwsze – co to, jak sprawdzić pierwszość oraz implementacja algorytmów

Ciąg Fibonacciego: algorytm, schemat blokowy i kalkulator

Szyfr Cezara – jak zrobić szyfrowanie i dekodowanie oraz implementacje

Dbamy o prywatność Twoich danych

Mapa witryny: Korepetycje z informatyki

Polecane wpisy na blogu poświęconemu nauce informatyki