15 SITO ERATOSTENESA

Sito Eratostenesa to algorytm za pomocą, którego jesteśmy w stanie w szybki sposób wyznaczyć liczby pierwsze z przedziału od 2 do n, gdzie n jest górną granicą przedziału. Stworzenie algorytmu przypisuje się Grekowi, Eratostenosowi z Cyreny.

DZIAŁANIE

Tworzymy tablicę i wypełniamy ją jedynkami. Bierzemy najmniejszy indeks (czyli dwa) i ustawiamy wartości wszystkich komórek, których indeksy są wielokrotnościami dwójki na fałsz. W dalszej kolejności postępujemy tak z następnym niewykreślonym indeksem, czyli trójką i analogicznie jak w przypadku dwójki ustawiamy wartości komórek o indeksach równych i*3 na fałsz.

W ten sposób postępujemy, dopóki obierany indeks będzie mniejszy lub równy pierwiastkowi z n.

#include <iostream>

using namespace std;
int tab[1000000];
int main(){
    for(int i=2;i<=1000000;i++)
        tab[i]=1;                //WYPEŁNIAMY CAŁĄ TABLICĘ JEDYNKAMI (ustawiamy jako prawda)
    
    for(int i=2;i*i<=1000000;i++){
        if(tab[i]==1){            
            for(int j=2;j*i<=1000000;j++)
                tab[j*i]=0;
        }
    } 

Jeżeli pod danym indeksem jest 1, wówczas wykreślamy wielokrotności liczby z indeksu (dla 2 wykreślamy 4,6,8,10,12…1000000 ),zamieniamy wartości "indeksów" na 0.

Sito bardzo dobrze opisane jest na stronie https://www.algorytm.edu.pl/algorytmy-maturalne/sito-eratostenesa.html

OMÓWIENIE ZADANIA DYZIO

Zadanie Dyzio: https://themis.ii.uni.wroc.pl/202324SP76KL7/DYZIO

Na wejściu dostajemy (w najgorszym wypadku) 20 000 zestawów zapytań o przedziały

$[a,b]$,

$1\le a,b\le 1000000$.Dla każdego z zapytań chcemy odpowiedź na pytanie: ,Ile jest liczb pierwszych niemniejszych od a i niewiększych od b?''.

Pierwsza przymiarka:

Pierwszą opcją byłoby policzenie wyniku ręcznie dla każdego przedziału.
Dla każdego przedziału

$[a,b]$, dla każdej liczby naturalnej z tego przedziału liczymy, czy jest ona liczbą pierwszą. Umiemy już dla liczby

$k$ sprawdzić w mniej więcej

$\sqrt{k}$ operacjach, czy jest pierwsza.
Przykładowy kod mógłby wyglądać następująco:

#include <iostream>

using namespace std;
bool pierwsza(int x){
    if(x<2) return false;
    for(int i=2; i*i<=x; i++){
        if(x%i==0) return false;
    }
    return true;
}
int main(){
   int n;
    cin>>n;
    while(n>0){
        int a, b, wynik=0;
        cin>>a>>b;
        for(int i=a; i<=b; i++){
            if(pierwsza(i)) wynik++;
        }
        cout<<wynik<<endl;
        n--;
    }

W powyższym rozwiązaniu dla każdego z (być może) 20000 przedziałów, dla każdej liczby z przedziału (przedział może mieć 1000000 liczb!) sprawdzamy, czy taka liczba jest pierwsza (co też zajmuje czas jako, że

$\sqrt{1000000}=1000$- od 1 do 1000 operacji).
Łącznie więc ten program wykona mniej więcej $20000 * 1000000 * 10000000000000 operacji. Bardzo dużo.

Drugie podejście:

Wiemy już, jak policzyć sito Eratostenesa - a zatem jak w mniej-więcej

$1000000\ast \sqrt{1000000}=1000000000$ operacjach wiedzieć o każdej liczbie, czy jest pierwsza, czy też nie.

Możemy więc policzyć sito Eratostenesa, a później wczytując zapytanie (przedział) wyliczać, ile liczb pierwszych się tam pojawiło.

W najgorszym przypadku policzymy sito w

${10}^9$ operacjach, a następnie dla każdego z

$2\ast {10}^4$ zapytań przejdziemy pętlą po milionie liczb (od 1 do 1000000). Wciąż jest to mniej-więcej

$2\ast {10}^{10}$ operacji.

Rozwiązanie:

Z pomocą przychodzi inny temat omawiany na zajęciach: sumy prefiksowe. Mając policzone sito, możemy policzyć (i zapamiętać w tablicy) dla każdej wartości

$x$, ile jest liczb pierwszych niewiększych od

$x$.

Następnie dostając zapytanie o przedział

$[a,b]$ wystarczy znaleźć w tablicy, ile jest liczb pierwszych nie większych od

$b$ oraz ile jest takich, które są mniejsze od

$a$ (niewiększe od

$a-1$).

Wartości początkowych pól obu tablic powinny wyglądać tak:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
0	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0	0
0	0	1	2	2	3	3	4	4	4	4	5	5	6	6	6	6

Liczba operacji potrzebna na policzenie wartości w drugiej tablicy to mniej więcej

${10}^6$. Mając sito Eratostenesa policzone w tablicy ,sito'', drugą tablicę liczymy następująco:

// (...)
ilePierwszych[0]=0;
for(int i=1; i<= 1000000; i++){
    ilePierwszych[i]=ilePierwszych[i-1];
    if(sito[i]==1){
        ilePierwszych[i]++;
    }
}
/

Wynikiem dla przedziału

$[a,b]$ jest ilePierwszych[b]-ilePierwszych[a-1];

OMÓWIENIE ZADANIA ROZKŁAD NA CZYNNIKI PIERWSZE 2

https://themis.ii.uni.wroc.pl/202324SP76KL7/E_FAC2

W zadaniu dostajemy

$t\le 500000$ zapytań, każde składa się z jednej liczby. Należy wypisać po kolei czynniki pierwsze tej liczby.

Pierwsza przymiarka:

Oczywiście podobnie jak w poprzednim zadaniu, gdy dostaniemy zapytanie o liczbę

$x$, możemy dla każdej liczby sprawdzać czy jest ona dzielnikiem

$x$, następnie wypisywać ją i zmniejszać

$x$. Kod mógłby wyglądać tak:

#include <iostream>
using namespace std;
int n, x;
int main(){
    cin>>n;
    while(n>0){
        cin>>x;
        int i=2;
        while(x>1){
            while(x%i==0){ //Tu na pewno i jest liczbą pierwszą. 
                //Gdyby nie była, to wcześniej podzelimy x przez jej 
                //dzielniki i i już nie będzie dzielnikiem x.
                cout<<i<<" ";
                x/=i;
            }
            i++;
        }
        n--;
    }
    
}

Podobnie jak w poprzednim zadaniu - takie rozwiązanie jest poprawne, ale za wolne.
Być może nie musimy za każdym razem szukać dzielnika…

Rozwiązanie:

Wyobraźmy sobie, że licząc sito zapamiętujemy więcej niż tylko zera i jedynki. Że dla liczby złożonej, zapamiętamy jej najmniejszy dzielnik.
Jak to zrobić? Wystarczy dla każdej liczby złożonej

$x$ zapamiętać, jaka liczba pierwsza ją ,skreśliła''.

Przykładowy początek tablicy:

2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
1	1	2	1	2	1	2	3	2	1	2	1	2	3	2	1	2

Wartość w 15 to 3, gdyż 3 jest najmniejszym pierwszym dzielnikiem 15. 3 ,skreśliło'' 15.

Mając taką tablicę i zapytanie o dzielniki liczby

$x$ możemy po prostu wypisać

$sito[x]$, a następnie zmniejszyć

$x=x/sito[x]$ I wykonywać tak aż

$x$ stanie się jedynką.

Jak policzyć taką tablicę?

#include <iostream>

using namespace std;
int tab[1000000];
int main(){
    for(int i=2;i<=1000000;i++)
        tab[i]=1;                //WYPEŁNIAMY CAŁĄ TABLICĘ JEDYNKAMI (ustawiamy jako prawda)
    
    for(int i=2;i*i<=1000000;i++){
        if(tab[i]==1){            
            for(int j=2;j*i<=1000000;j++)
                if(tab[j*i]==1){
                    tab[j*i]=i;
                }
        }
    }