Cel mai mic divizor prim: ciur și interogări C++

Dacă trebuie să afli cel mai mic divizor prim pentru multe numere, repetarea împărțirilor de probă poate face aceeași muncă de multe ori. Putem pregăti un tablou o singură dată, apoi răspunde printr-un acces direct. Pentru 12 răspunsul este 2, pentru 35 este 5, iar pentru 17 este chiar 17.

Ce păstrează tabloul SPF

SPF este abrevierea engleză pentru smallest prime factor, adică cel mai mic factor prim. Citim limita L, cu 2≤L≤100000, numărul q de întrebări, cu 1≤q≤1000, apoi q valori din intervalul 2..L. Afișăm pentru fiecare valoare factorul prim minim. Numerele 0 și 1 sunt excluse deoarece nu au factori primi.

Tabloul clasic are capacitatea 100001. Folosim indicii 2..L pentru răspunsuri; pozițiile 0 și 1 nu reprezintă întrebări valide. Inițial, valoarea zero înseamnă că factorul nu a fost încă atribuit.

Prima atribuire câștigă

Parcurgem p în ordine crescătoare. Dacă spf[p] este zero, p este prim: un număr compus ar fi fost marcat de un factor prim mai mic. Vizităm multiplii lui p și scriem p numai în celulele încă necompletate. O atribuire ulterioară ar pierde tocmai proprietatea de minim.

Factorii sunt examinați crescător. Prima atribuire fixează minimul.Mărește schema ↗

Pentru 12, trecerea prin p=2 fixează răspunsul 2. Când ajungem la p=3, nu îl înlocuim cu 3. Pentru un număr prim precum 17, primul său multiplu vizitat în acest proces este chiar 17, deci primește propria valoare.

Program complet cu tablou clasic

#include <iostream>
using namespace std;
int main(){
    int limita,q; cin>>limita>>q;
    int spf[100001]{};
    for(int p=2;p<=limita;++p){
        if(spf[p]==0){
            for(int x=p;x<=limita;x+=p){
                if(spf[x]==0) spf[x]=p;
            }
        }
    }
    for(int i=0;i<q;++i){
        int x;cin>>x;
        cout<<spf[x]<<'\n';
    }
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării, indexarea și rezultatele. Tabloul clasic rezervă capacitatea maximă, iar n descrie numărul elementelor folosite. Varianta vector păstrează aceeași dimensiune logică; accesul prin [] cere în continuare indici valizi.

#include <vector>
#include <iostream>
using namespace std;
int main(){
    int limita,q; cin>>limita>>q;
    vector<int> spf(limita+1,0);
    for(int p=2;p<=limita;++p){
        if(spf[p]==0){
            for(int x=p;x<=limita;x+=p){
                if(spf[x]==0) spf[x]=p;
            }
        }
    }
    for(int i=0;i<q;++i){
        int x;cin>>x;
        cout<<spf[x]<<'\n';
    }
}

Cost și utilizare

Fiecare atribuire reținută vine de la cel mai mic prim care divide indicele. Ordinea crescătoare și regula de a nu suprascrie demonstrează corectitudinea. Pregătirea acestei variante de ciur are timp O(L log log L), iar fiecare întrebare are O(1). Memoria tabloului este O(L). Pentru o singură valoare foarte mare, un astfel de tablou poate fi nepotrivit.

Exersează

Pentru limita 20 și întrebările 2,12,17,20, răspunsurile sunt 2,2,17,2. Modifică ideea pentru descompunere: afișează spf[x], împarte x la acel factor și repetă până când x devine 1. Pentru 12 obții factorii 2,2,3.

Recapitulează ciurul lui Eratostene, factorizarea și tablourile de frecvență.

Întrebări frecvente

Ce înseamnă SPF în algoritmii pe numere?

Smallest prime factor, adică cel mai mic factor prim al unui număr. Tabloul SPF asociază fiecărui număr din domeniul pregătit acest factor.

De ce nu suprascriu un factor prim deja memorat?

Primii sunt parcurși crescător. Prima valoare atribuită este deja cea mai mică; un factor ulterior poate divide numărul, dar nu poate îmbunătăți minimul.

Ce valoare SPF are un număr prim?

Numărul însuși, deoarece singurul său divizor prim este chiar el. Pentru 0 și 1 această noțiune nu este definită în contractul lecției.