Informatyka. Konkursy i algorytmy
sito Eratostenesa
Do czego służy?
Sito Eratostenesa służy do określenia dla wszystkich liczb do jakiejś liczby, czy są pierwsze czy nie. Czyli, mamy liczbę n (nie może być większe od pojemności tablicy) i za pomocą sita Eratostenesa możemy określić w szybkim czasie czy są pierwsze czy nie dla wszystkich liczb <= n.
Algorytm
Tworzymy tablicę o długości n, gdzie komórka o numerze i będzie odpowiadać za to, czy i
jest pierwsze czy nie. Tablicę na początku wypełniamy zerami. 0 będzie odznaczać że
liczba jest pierwsza, a 1 że liczba jest niepierwsza. Komórki 0 i 1 od razu ustawiamy
na 1(te liczby nie są pierwsze). Następnie przechodzimy od 2 do pierwiastka kwadratowego
z n. Podczas tej iteracji występujemy następujące kroki:
1. Jeżeli w tablicy na indeksie określonym liczbą, w której aktualnie jesteśmy jest 1,
to pomijamy dalszą część kroków. W przeciwnym wypadku przechodzimy do dalszej części
algorytmu.
2. Iterujemy się po liczbach od i2 do sqrt2(n)
"skacząc" co i (i to jest liczba, w której aktualnie jesteśmy). Dla każdej liczby, do
której "wskoczymy" ustawiamy wartość w tablicy na 1.
Czemu tak? Zauważmy, że "skacząc" co i odwiedzamy same wielokrotności i, a
wielokrotności jakiejś liczby nie mogą być liczbami pierwszymi. A skąd warunek na
początku? Skoro jakaś liczba została już zaznaczona 1, to znaczy, że jakaś liczba x jest
jej dzielnikiem. A wszystkie liczby podzielne przez liczbę złożoną są też podzielne przez
jakąś liczbę pierwszą mniejszą od tej liczby. Z kolei jeśli jakiejś liczby jeszcze nie
zaznaczyliśmy, to znaczy że jest pierwsza (żadna liczba nie może być podzielna przez
większą od siebie, a mniejsze już rozpatrzyliśmy). Czemu "skaczemy" od i2?
Zauważmy, że mniejsze liczby były już na pewno odwiedzone - mają dzielniki < i. Czemu
przechodzimy się tylko do sqrt2(n)? Większe liczby będą miały i2
większe od n, a chcemy mieć liczby tylko do n.
Przykład
Zasymulujmy sito Eratostenesa dla n = 20.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (indeksy tablicy)
0 0 0 0 0 0 0 0 0 00000
0 00 00
00
(wartości w tablicy)
1 1 0 0 0 0 0 0 0 00000
0 00 00
00
1 1 0 0 1 0 1 0 1 01010
1 01 01
01
1 1 0 0 1 0 1 0 1 11010
1 11 01
01
Zauważmy, że następna liczba, 4 ma już 1, więc ją pomijamy. Z kolei jeszcze następna, 5
jest mniejsza od sqrt2(20), więc kończymy algorytm.
Implementacja i złożoność
implementacja w c++:int liczby_pierwsze[MAXI];
bool lp[1000000007];
void SitoEratostenesa(){
int i;
int maxi = sqrt(MAXI) + 1;
liczby_pierwsze[0] = 1;
liczby_pierwsze[1] = 1;
for(i = 2; i < maxi; i++){
if (liczby_pierwsze[i] == 1){
continue;
}
for (int j = i * i; j < MAXI; j +=i ){
liczby_pierwsze[j] = 1;
}
}
}
implementacja w python:
liczby_pierwsze = [True for i in range(1000007)]
def SitoEratostenesa():
maxi = ceil(sqrt(1000007))
liczby_pierwsze[0] = False
liczby_pierwsze[1] = False
for i in range(2, maxi):
if(liczby_pierwsze[i] == False):
continue
for j in range(i * i, 1000007, i):
liczby_pierwsze[j] = False
złożoność: