O metoda interesanta de rezolvare a acestei probleme este metoda lui Erastotene de gasire a numerelor prime.
Metoda lui afla toate numerele prime pana la un numar n, dar este evident ca poate fi adaptata pentru cazul tau.
Ce spune metoda este urmatoarea:
Pentru a afla numerele prime intre 1 si n, ia numarul i=2, si apoi noteaza toti multiplii lui i din sir. Daca n ar fi 12, acei multipli ar fi: 2,4,6,8,10,12.
Apoi, du-te la urmatorul numar care nu a fost marcat, si reincepe procesul de marcare al multiplilor
Dupa cum vezi 3 nu a fost marcat, atunci luam toti multiplii lui 3: 3,6,9,12, deci practic mai marcat doar pe 9 aditional
Si asa mai departe pana cand ajungi la [tex]\sqrt{n}[/tex] Observi ca numerele marcate nu sunt prime pentru ca sunt deja un multiplu al unul alt numar.
La sfarsit, toate numerele nemarcate, cele care au inceput sirul, vor fi numerele prime
In cazul nostru: 2,3,5,7 si 11 nu ar fi marcati(restul cifrelor deja i-am marcat)
In cazul tau, aplicam metoda lui Erastotene o singura data pentru q, si apoi eliminam toate numerele prime care sunt mai mici decat p
Deci pseudocodul ar fi cam urmatorul:
citeste p, citeste q
citeste vector[q] //vector care este umplut cu valoarea 0
//cand 0 sa avem o valoare de sters, o sa o notam cu 1
pentru(i=2;i<=radical(q);i++) executa
multiplu=2 //trebuie sa fie minim 2
cattimp(multiplu*i<=q) executa
vector[multiplu*i]=1
//treci la urmatorul multiplu
multiplu=multiplu+1
nr_valori_prime=0
pentru (i=p;i<=q,i=i+1) executa
daca(vector[i]==0) atunci
afiseaza i;
nr_valori_prime=nr_valori_prime+1;
//ai aflat numarul de valori prime si ai afisat numerele prime
//Iti adaug si programul in C++
