Sito Eratostenesa – liczby pierwsze
Sito Eratostenesa to sposób na wyznaczanie liczb pierwszych. Został odkryty w II p.n.e przez greckiego matematyka Eratostenesa. Jest jedną z najprostszych metod wyznaczania liczb pierwszych. Jest to zagadnienie często pojawiające się na maturach z informatyki.
Spis treści
Czym są liczby pierwsze
Liczby pierwsze – to liczby naturalne większe od 1, które posiadają dokładnie dwa dzielniki: liczbę 1 oraz samą siebie.
Dzielnikiem liczby jest taka liczba całkowita, która dzieli jakąś cyfrę bez reszty. Przykładowo liczba 3 jest liczbą pierwszą, ponieważ dzieli się tylko przez 1 oraz 3. Liczba 4 nie jest liczbą pierwszą, ponieważ dzieli się przez 1, 2 oraz 4.
Liczby pierwsze znajdują w informatyce wiele zastosowań. Dzięki temu, że nie wymyślono wzoru na liczby pierwsze, opiera się na nich cała kryptografia. Ostatnie badania wskazują, że rozmieszczenie liczb pierwszych w zbiorze liczb naturalnych wskazuje pewne powtarzalne prawidłowości, jednak wzór nie został odkryty.
Jedyna znana metoda wyznaczania liczb pierwszych to sito Eratostenesa, jednak nie jest ona zbyt wydajna.
Sito Eratostenesa
Za pomocą algorytmu Eratostenesa możemy wyznaczyć dowolną ilość liczb pierwszych z przedziału \([2,15]\). Założenie działania algorytmu jest dość proste. Zbiór liczb naturalnych składa się z liczb złożonych oraz liczby pierwszych.
Liczby naturalne – to wszystkie liczy całkowite, dodatnie (np. 1,2,3,4…)
Liczby złożone – to wszystkie liczby naturalne, które posiadają więcej niż dwa dzielniki (np. 4, 6, 9, 10, 12, 14, 15, 16…)
Jeżeli liczba naturalna nie jest złożona – to jest pierwsza. Jeżeli liczba naturalna nie jest pierwsza – to jest złożona. Gdy ze zbioru liczb naturalnych usuniemy wszystkie liczby złożone, wtedy otrzymamy zbiór liczb pierwszych. To podstawowa zasada działania algorytmu sita Eratostenesa.
Działanie algorytmu
Działanie algorytmu polega na tym, aby z danego zbioru liczb naturalnych usunąć wszystkie liczby złożone. W praktyce polega to na tym, aby usunąć wszystkie wielokrotności liczb 2, 3, 5 i 7.
Przykład
Przyjmijmy, że chcemy wyznaczyć wszystkie liczby pierwsze z zakresu 1-15. W takim razie, będzie nas interesował zbiór \([2,15]\).
Z powyższego zbioru usuńmy wszystkie wielokrotności liczby 2, oprócz liczby 2:
Teraz, usuńmy wszystkie wielokrotności liczby 3, oprócz liczby 3:
W kolejnym kroku powinniśmy usunąć wszystkie wielokrotności liczby 4, jednak one zostały już usunięte przy usuwaniu wielokrotności 2. W kolejnym kroku usuńmy wszystkie wielokrotności liczby 5 (akurat w naszym zbiorze nie ma nic do usunięcia):
W kolejnym kroku powinniśmy usunąć wszystkie wielokrotności liczby 6, jednak one zostały usunięte podczas usuwania wielokrotności 3. Następnie usuńmy wszystkie wielokrotności 7, pomijając liczbę 7 (akurat w naszym zbiorze nie ma nic do usunięcia):
Więcej, kroków już nie ma, ponieważ liczba 8 to wielokrotności 2, liczba 9 wielokrotności 3. W ten sposób z naszego zbioru liczb \([2,15]\) pozbyliśmy się wszystkich liczb złożonych. Wszystkie liczby, które zostały, to liczby pierwsze:
Takim oto prostym sposobem, jesteś w stanie bez żadnego problemu wyznaczyć dowolną ilość liczb pierwszych.
Kod programu w C++
Istnieją różne sposoby implementacji algorytmu Eratostenesa. Moim zdaniem na maturę z informatyki najlepsza będzie ta poniżej. Kilka osobnych pętli, z których każda usuwa wielokrotność liczb 2, 3, 5 oraz 7. Taki dłuższy zapis jest najłatwiej zapamiętać i później odtworzyć, eliminując pomyłkę.
#include <iostream>
using namespace std;
int main()
{
int przedzial = 100;
bool liczby[przedzial];
// inicjalizacja tablicy
for (int i = 0; i < przedzial; i++)
liczby[i] = false;
// usuwamy wielokrotnosci 2 (oprócz 2)
for (int i = 4; i <= przedzial; i = i + 2)
liczby[i] = true;
// usuwamy wielokrotnosci 3 (oprócz 3)
for (int i = 6; i <= przedzial; i = i + 3)
liczby[i] = true;
// usuwamy wielokrotnosci 5 (oprócz 5)
for (int i = 10; i <= przedzial; i = i + 5)
liczby[i] = true;
// usuwamy wielokrotnosci 7 (oprócz 7)
for (int i = 14; i <= przedzial; i = i + 7)
liczby[i] = true;
cout << "Liczby pierwsze z przedzialu 2 do " << przedzial << endl;
for (int i = 2; i <= przedzial; i++)
{
if (liczby[i] == false)
{
cout << i << ", ";
}
}
system("PAUSE >nul");
return 0;
}
Powyższe podejście jest łatwe do zapamiętania, jednak jest dość niewydajne. Kilkukrotnie przechodzimy przez tablicę wykonując, całkiem niepotrzebnie, te same operacje.
Na wikipedii dostępna jest bardziej wydajna wersja wersja algorytmu. Optymalizacja polega na wykorzystaniu własności liczb złożonych, polegającej na tym, że wielokrotności liczb złożonych zawsze są liczbami złożonymi. Co można zoptymalizować:
- Pętla może działać w przedziale \(2..\sqrt{n}\) zamiast \(2..n\)
- Przed usuwaniem danej wielokrotności, sprawdzić czy nie została już usunięta
- Zaczynać usuwanie od potęgi danej wielokrotności
Kod po optymalizacji może wyglądać np. tak:
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int przedzial = 100;
bool liczby[przedzial];
// inicjalizacja tablicy
for (int i = 0; i < przedzial; i++)
liczby[i] = false;
// usuwanie wielokrotnosci
for (int i = 2; i <= sqrt(przedzial); i++)
{
if (liczby[i] == false)
{
for (int j = i * i; j <= przedzial; j += i)
{
liczby[j] = true;
}
}
}
cout << "Liczby pierwsze z przedzialu 2 do " << przedzial << endl;
for (int i = 2; i <= przedzial; i++)
{
if (liczby[i] == false)
{
cout << i << ", ";
}
}
system("PAUSE >nul");
return 0;
}
Sprawdzanie czy liczba jest pierwsza
Korzystanie z algorytmu Eratostenesa doskonale sprawdza się, aby wyznaczyć kilka liczb pierwszych. Jeżeli chcemy przetestować czy konkretna liczba naturalna jest liczbą pierwszą, korzystanie z powyższego algorytmu nie jest potrzebne.
Wystarczy napisać prosty program, który sprawdzi czy wpisana liczba nie ma innych dzielników naturalnych, czyli takich, które dzielą liczbę bez reszty. W tym celu skorzystamy z operatora dzielenia modulo:
#include <iostream>
using namespace std;
int main()
{
int liczba;
cout << "Wpisz liczbe" << endl;
cin >> liczba;
if (liczba <= 1)
{
cout << "Liczba nie jest liczba pierwsza" << endl;
}
else
{
for (int i = 2; i < liczba; i++)
{
if (liczba % i == 0)
{
cout << "Liczba nie jest liczba pierwsza" << endl;
system("PAUSE >nul");
return 0;
}
}
cout << "Liczba jest liczba pierwsza" << endl;
}
system("PAUSE >nul");
return 0;
}
