# 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 \leq a, b \leq 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 * \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 * 10^4$ zapytań przejdziemy pętlą po milionie liczb (od 1 do 1000000). Wciąż jest to mniej-więcej $2* 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 \leq 500 000$ 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;
                }
        }
    }