h3. (problema medie, clasa a 9a)

Fiind vorba de maxim $1.000.000$ numere se poate calcula pentru fiecare in parte cati divizori primi are. Pentru acest lucru se foloseste ciurul lui Erathostene si se construieste vectorul {$ndp{~i~}$} - numarul de divizori primi ai lui {$i$}. Parcurgem numerele din $1$ in $1$ si in momentul in care am dat peste un numar care are $0$ divizori primi pana in acest moment inseamna ca am gasit un nou numar prim si vom actualiza vectorul $ndp$ pentru toti multiplii lui si implicit pentru el (numarul fiind propriul sau divizor). Apoi se construieste o matrice $sol{~i,j~}$ care retine care este cel mai mare numaru mai mic sau egal cu $i$ cu $j$ divizori primi (adica exact raspunsurile pentru problema noastra). Pentru a construi linia $i$ se copiaza linia $i-1$ si se actualizeaza {$sol{~i,ndp{~i~}~}=i$}.

Fiind vorba de maxim $1.000.000$ numere se poate calcula pentru fiecare in parte cati divizori primi are. Pentru acest lucru se foloseste ciurul lui Erathostene si se construieste vectorul {$ndp{~i~}$} - numarul de divizori primi ai lui {$i$}. Parcurgem numerele din $1$ in $1$ si in momentul in care am dat peste un numar care are $0$ divizori primi pana in acest moment inseamna ca am gasit un nou numar prim si vom actualiza vectorul $ndp$ pentru toti multiplii lui si implicit pentru el (numarul fiind propriul sau divizor). Apoi se construieste o matrice $sol{~i,j~}$ care retine care este cel mai mare numar mai mic sau egal cu $i$ cu $j$ divizori primi (adica exact raspunsurile pentru problema noastra). Pentru a construi linia $i$ se copiaza linia $i-1$ si se actualizeaza {$sol{~i,ndp{~i~}~}=i$}.

Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa "articolul":http://infoarena.ro/Ciurul-lui-Erathostene.