Question

Va rog,am nevoie de o rezolvare in pseudocod. Sa se afiseze toate numerele prime situate in intervalul [p,q] precum si numarul acestora,unde p si q sunt nr naturale date.

Answer 1

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 $\sqrt{n}$ 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++

607a44add6ac8927b878fa6c2a25a653.cpp

Answer 2

#include <iostream>
using namespace std;
const int NMAX = 200000000;

int p, q, nr, v[NMAX];

int main()
{
    cin >> p >> q;
    for(int i=2; i<=q; i++) {
        if(!v[i]) {
            if(i >= p) { cout << i << ' '; nr++; }
            for(int j=i+i; j<=q; j+=i)
                v[j] = 1;
        }
    }
    cout << '\n' << nr << '\n';
}