Liczby pierwsze: tabela do 1000 i sito Eratostenesa

Liczby pierwsze to liczby naturalne większe od 1, które dzielą się tylko przez 1 i przez samą siebie, a mniejszych od 1000 jest dokładnie 168, od 2 do 997. Poniżej jest ich pełna tabela, odpowiedzi na pytania, które padają najczęściej w szkole, i dwa sposoby sprawdzania liczb w programie: dzielenie do pierwiastka i sito Eratostenesa. Kod w Pythonie i C++ uruchomiliśmy, a tabelę wygenerowaliśmy programem i porównaliśmy z ciągiem A000040 w encyklopedii ciągów OEIS.

Spis treści

1. Definicja i przykłady
2. Czy 1 jest liczbą pierwszą
3. Tabela do 1000
4. Pierwsze czy złożone
5. Jak sprawdzić, czy liczba jest pierwsza
6. Sito Eratostenesa w Pythonie i C++
7. Rozkład na czynniki pierwsze
8. Ile ich jest
9. Szyfrowanie RSA
10. Najczęstsze pytania

Liczba pierwsza: definicja i przykłady

Zintegrowana Platforma Edukacyjna definiuje to tak: “Liczbę naturalną, która ma tylko dwa dzielniki: jeden i samą siebie, nazywamy liczbą pierwszą”. Definicja wymaga dokładnie dwóch różnych dzielników i to ten warunek wyklucza jedynkę.

Przykłady z pierwszej dziesiątki: 2, 3, 5 i 7. Siódemka dzieli się bez reszty tylko przez 1 i 7. Dziewiątka ma trzy dzielniki (1, 3 i 9), więc pierwsza nie jest. Z kolei 91 wygląda na pierwszą, ale 91 = 7 · 13.

Każdą liczbę naturalną większą od 1 da się zapisać jako iloczyn liczb pierwszych, i to tylko na jeden sposób, jeśli nie liczyć kolejności czynników. Na tym opiera się rozkład na czynniki pierwsze, opisany niżej.

Czy 1 jest liczbą pierwszą? Pytania z jedną odpowiedzią

Czy 1 jest liczbą pierwszą?

Nie. Jedynka ma tylko jeden dzielnik, czyli samą siebie, a liczba pierwsza musi mieć dwa. ZPE zaznacza wprost, że liczba 1 nie jest ani pierwsza, ani złożona.

Czy 0 jest liczbą pierwszą?

Nie. Zero dzieli się przez każdą liczbę naturalną dodatnią, więc ma nieskończenie wiele dzielników. Według ZPE nie jest ani pierwsze, ani złożone.

Jaka jest najmniejsza liczba pierwsza?

Najmniejsza liczba pierwsza to 2. Najmniejsza nieparzysta to 3, najmniejsza dwucyfrowa to 11, a najmniejsza trzycyfrowa to 101.

Czy 2 jest jedyną parzystą liczbą pierwszą?

Tak. Każda inna liczba parzysta dzieli się przez 1, przez 2 i przez samą siebie, więc ma co najmniej trzy dzielniki. Dlatego programy sprawdzające pierwszość odrzucają parzyste liczby od razu i testują tylko nieparzyste.

Tabela liczb pierwszych do 1000

Poniżej wszystkie 168 liczb pierwszych mniejszych od 1000, pogrupowane w setki. Tabelę wygenerował program z sitem Eratostenesa i sprawdziliśmy ją drugim algorytmem, dzieleniem próbnym, a potem z listą OEIS.

W pierwszej setce jest 25 liczb pierwszych, w ostatniej już tylko 14. Im dalej, tym rzadziej się pojawiają, ale nigdy się nie kończą, co pokazujemy niżej. Największa liczba pierwsza mniejsza od 1000 to 997.

Pierwsza Misja AI · Kodożercy

Pierwszy raz z AI? Zaczynasz od zera.

Pierwsza Misja AI to kurs dla osób bez technicznego przygotowania. Nie musisz pisać kodu ani znać żargonu. Dowiesz się, jak działa AI, jak promptować i jak korzystać z niej w pracy.

Wejdź na pokład →

Liczby pierwsze i złożone: jak je odróżnić

Liczba złożona to liczba naturalna różna od zera, która ma więcej niż dwa dzielniki, na przykład 4, 6, 9 albo 91. Każda liczba naturalna większa od 1 jest albo pierwsza, albo złożona. Poza tym podziałem zostają tylko 0 i 1.

Przy liczbach do 100 wystarczą trzy szybkie testy, zanim zaczniesz dzielić:

• liczba parzysta większa od 2 jest złożona, bo dzieli się przez 2;
• jeśli suma cyfr dzieli się przez 3, liczba dzieli się przez 3 (na przykład 51, bo 5 + 1 = 6, a 51 = 3 · 17);
• liczba zakończona na 0 albo 5, większa od 5, dzieli się przez 5.

Nie myl liczb złożonych z liczbami względnie pierwszymi. Względnie pierwsze to para liczb, których największy wspólny dzielnik wynosi 1, na przykład 8 i 15. Obie są złożone, ale nie mają wspólnego dzielnika poza jedynką. NWD liczy się algorytmem Euklidesa, który rozpisaliśmy w tekście o NWD i NWW w Pythonie i C++.

Jak sprawdzić, czy liczba jest pierwsza

Żeby sprawdzić, czy liczba n jest pierwsza, wystarczy podzielić ją przez kolejne liczby od 2 do pierwiastka z n. Jeśli żadne dzielenie nie wyjdzie bez reszty, liczba jest pierwsza. Wyżej szukać nie trzeba, bo każdy dzielnik większy od pierwiastka ma do pary dzielnik mniejszy od pierwiastka.

Przykład dla 997. Pierwiastek z 997 to około 31,6, więc sprawdzamy dzielniki do 31. Żaden nie dzieli 997 bez reszty, więc 997 jest pierwsza. Dla 91 pierwiastek to około 9,5, a dzielenie przez 7 daje 13, więc 91 jest złożona.

Ta sama metoda w Pythonie. Najpierw odrzucamy liczby mniejsze od 2 i parzyste, potem sprawdzamy tylko nieparzyste dzielniki:

def czy_pierwsza(n):
    """Sprawdza, czy n jest liczbą pierwszą (dzielenie do pierwiastka)."""
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True


print(czy_pierwsza(97), czy_pierwsza(91))

Wynik: True False. Warunek d * d <= n zastępuje liczenie pierwiastka i nie ma problemu z zaokrągleniami liczb zmiennoprzecinkowych. Dla jednej liczby to wystarczy: przy n około miliona program wykona najwyżej kilkaset dzieleń. Gdy potrzebujesz wszystkich liczb pierwszych z przedziału, szybsze jest sito.

Sito Eratostenesa: jak działa

Sito Eratostenesa znajduje wszystkie liczby pierwsze do n przez wykreślanie wielokrotności kolejnych liczb pierwszych. To, co zostanie niewykreślone, jest pierwsze. Nazwa pochodzi od greckiego uczonego Eratostenesa, któremu tradycja przypisuje tę metodę.

Kroki dla liczb do n:

1. Wypisz liczby od 2 do n.
2. Weź najmniejszą niewykreśloną liczbę. Jest pierwsza.
3. Wykreśl wszystkie jej wielokrotności, zaczynając od jej kwadratu.
4. Wróć do kroku 2, dopóki kwadrat wziętej liczby nie przekroczy n.

Dla n = 100 wystarczą cztery przejścia: przez 2, 3, 5 i 7. Następna liczba pierwsza to 11, a 11² = 121 jest już większe od 100. Wykreślanie zaczyna się od kwadratu, bo mniejsze wielokrotności, na przykład 3 · 7 = 21, wykreśliło już przejście przez mniejszą liczbę pierwszą. Ten sam opis z przykładem dla n = 30 podaje ZPE w materiale o sicie Eratostenesa.

Sito Eratostenesa w Pythonie

Program trzyma tablicę wartości logicznych pierwsza, w której indeks to liczba, a wartość mówi, czy liczba nie została jeszcze wykreślona:

def sito_eratostenesa(n):
    """Zwraca listę liczb pierwszych od 2 do n."""
    if n < 2:
        return []
    pierwsza = [True] * (n + 1)
    pierwsza[0] = pierwsza[1] = False
    p = 2
    while p * p <= n:
        if pierwsza[p]:
            for k in range(p * p, n + 1, p):
                pierwsza[k] = False
        p += 1
    return [i for i in range(n + 1) if pierwsza[i]]


print(sito_eratostenesa(100))
print(len(sito_eratostenesa(1000)))

Wynik w Pythonie 3.14:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
168

Sito Eratostenesa w C++

Wersja w C++ robi to samo na std::vector<bool>. Zmienne pętli mają typ long long, żeby p * p nie przekroczyło zakresu int przy dużym n. W funkcji czy_pierwsza warunek d <= n / d zastępuje d * d <= n, bo dla liczb bliskich górnej granicy long long iloczyn mógłby przekroczyć zakres typu:

#include <iostream>
#include <vector>

std::vector<int> sito_eratostenesa(int n) {
    std::vector<int> wynik;
    if (n < 2) return wynik;
    std::vector<bool> pierwsza(n + 1, true);
    pierwsza[0] = pierwsza[1] = false;
    for (long long p = 2; p * p <= n; ++p) {
        if (pierwsza[p]) {
            for (long long k = p * p; k <= n; k += p) {
                pierwsza[k] = false;
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (pierwsza[i]) wynik.push_back(i);
    }
    return wynik;
}

bool czy_pierwsza(long long n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (long long d = 3; d <= n / d; d += 2) {
        if (n % d == 0) return false;
    }
    return true;
}

int main() {
    for (int p : sito_eratostenesa(100)) std::cout << p << ' ';
    std::cout << '\n' << sito_eratostenesa(1000).size() << '\n';
    std::cout << czy_pierwsza(97) << ' ' << czy_pierwsza(91) << '\n';
    return 0;
}

Wynik w konsoli (GCC 14.4, -std=c++17 -O2 -Wall):

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
168
1 0

Sito czy dzielenie: co jest szybsze

Sito wykonuje około n · log log n operacji i potrzebuje pamięci na n + 1 wartości. Opłaca się, gdy chcesz wszystkich liczb pierwszych z przedziału, na przykład do tabeli albo do wielu zapytań. Dzielenie do pierwiastka potrzebuje około √n dzieleń na jedną liczbę i nie zużywa dodatkowej pamięci. Lepiej sprawdza się przy pojedynczych, dużych liczbach. Jak porównuje się złożoność algorytmów, wyjaśniamy w tekście o rodzajach algorytmów i ich złożoności, a jak rozpisać taką pętlę na diagramie, w poradniku o schemacie blokowym.

Rozkład na czynniki pierwsze krok po kroku

Rozkład na czynniki pierwsze to zapisanie liczby jako iloczynu liczb pierwszych. Dzielisz liczbę przez najmniejszą liczbę pierwszą, która ją dzieli, i powtarzasz to z wynikiem, aż zostanie 1.

Przykład dla 360, rozpisany jak w zeszycie:

Czynniki z kolumny “Dzielnik” dają rozkład 360 = 2 · 2 · 2 · 3 · 3 · 5, czyli w zapisie potęgowym 2³ · 3² · 5. Inne przykłady: 84 = 2² · 3 · 7, 999 = 3³ · 37, 1001 = 7 · 11 · 13. Liczba pierwsza, na przykład 997, ma rozkład złożony z niej samej.

Ta sama procedura w Pythonie:

def rozklad(n):
    """Rozkład liczby n >= 2 na czynniki pierwsze."""
    czynniki = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            czynniki.append(d)
            n //= d
        d += 1
    if n > 1:
        czynniki.append(n)
    return czynniki


print(rozklad(360), rozklad(1001))

Wynik: [2, 2, 2, 3, 3, 5] [7, 11, 13]. Pętla nie musi pomijać dzielników złożonych, takich jak 4 czy 6, bo zanim do nich dojdzie, wszystkie dwójki i trójki są już wydzielone. Z rozkładu na czynniki da się też policzyć NWD i NWW bez komputera, co pokazujemy w tekście o algorytmie Euklidesa.

Ile jest liczb pierwszych?

Liczb pierwszych jest nieskończenie wiele. Dowód podał Euklides w “Elementach” (księga IX, twierdzenie 20, wydanie D. E. Joyce’a). Weź dowolną skończoną listę liczb pierwszych, pomnóż je i dodaj 1. Wynik nie dzieli się przez żadną liczbę z listy, więc albo sam jest pierwszy, albo ma dzielnik pierwszy spoza listy.

Rzedną jednak w miarę wzrostu. Do 100 jest ich 25, do 1000 jest 168, a do 100 000 jest 9592, czyli niecałe 10% liczb. Ich liczbę do n przybliża wzór n / ln n z twierdzenia o liczbach pierwszych. Dla n = 100 000 daje on około 8686, mniej więcej 9% mniej niż faktycznie.

Zastosowanie w informatyce: szyfrowanie RSA

Najważniejsze zastosowanie liczb pierwszych w informatyce to kryptografia z kluczem publicznym, zwłaszcza RSA. Dwie duże liczby pierwsze służą do obliczenia modułu, czyli ich iloczynu, który jest częścią klucza publicznego i prywatnego. Pomnożyć je jest łatwo, a rozłożyć wynik z powrotem na czynniki przy odpowiednio długim kluczu nie da się w rozsądnym czasie. ZPE wskazuje właśnie trudność rozkładu dużych liczb na czynniki pierwsze jako źródło bezpieczeństwa RSA i jego zastosowanie w podpisach cyfrowych. Bezpieczeństwo zależy przy tym od długości klucza: krótki klucz da się rozłożyć.

Dla porównania szyfr Cezara ma tylko kilkadziesiąt możliwych kluczy i łamie się go, sprawdzając wszystkie po kolei, co pokazujemy w tekście o szyfrze Cezara.

Najczęstsze pytania

Jaka jest największa znana liczba pierwsza?

Według listy projektu GIMPS (stan na 19 października 2026 roku) to 2^136 279 841 − 1, liczba o 41 024 320 cyfrach. Udowodnił jej pierwszość Luke Durant 12 października 2024 roku, a GIMPS ogłosił ją 21 października 2024 roku. To liczba Mersenne’a, czyli liczba postaci 2^p − 1. Informacje podaje strona projektu GIMPS.

Czym są liczby pierwsze bliźniacze?

To pary liczb pierwszych różniących się o 2. Poniżej 100 jest ich osiem: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) i (71, 73). Nie wiadomo, czy takich par jest nieskończenie wiele. To wciąż nierozstrzygnięta hipoteza liczb pierwszych bliźniaczych, a ciąg mniejszych liczb z tych par prowadzi OEIS jako A001359.

Ile jest liczb pierwszych do 100?

Do 100 jest 25 liczb pierwszych: od 2 do 97. Wszystkie są w pierwszym wierszu tabeli i na siatce sita powyżej.

Jak szybko zapamiętać liczby pierwsze do 100?

Zapamiętaj cztery pierwsze: 2, 3, 5 i 7. Każda liczba od 11 do 100, która nie dzieli się przez żadną z nich, jest pierwsza, bo 11² = 121 jest już większe od 100.

Podsumowanie

Liczby pierwsze to liczby naturalne większe od 1 z dokładnie dwoma dzielnikami: jedynką i samą sobą. Jedynka i zero do nich nie należą, najmniejszą liczbą pierwszą jest 2 i jest to jedyna parzysta liczba pierwsza. Mniejszych od 1000 jest 168, a największa z nich to 997. Pojedynczą liczbę sprawdzisz, dzieląc ją przez kolejne liczby do pierwiastka. Wszystkie takie liczby z przedziału daje sito Eratostenesa, które wykreśla wielokrotności 2, 3, 5 i kolejnych liczb pierwszych, aż kwadrat następnej przekroczy n. Rozkład na czynniki pierwsze robi się tą samą metodą dzielenia, a w informatyce trudność takiego rozkładu dla bardzo dużych liczb chroni szyfrowanie RSA.

Mateusz Wojdalski

Specjalista SEO i content marketingu w Devstock. Zajmuję się strategią treści, automatyzacją procesów marketingowych i wdrożeniami AI w codziennej pracy. Badam nowe narzędzia, adaptuję je do realnych zadań i piszę o tym, co faktycznie działa.