Question

În fişierul text BAC.IN se găsesc, pe o singură linie, separate prin câte un spaţiu, mai multe numere naturale de cel mult 6 cifre fiecare. Se cere să se determine şi să se afişeze pe ecran, separate printr-un spaţiu, ultimele două numere prime (nu neapărat distincte) din fişierul BAC.IN. Dacă în fişier se găseşte un singur număr prim sau niciun număr prim se va scrie pe ecran mesajul Numere prime insuficiente.
Exemplu: dacă fişierul BAC.IN conţine valorile: 12 5 68 13 8 17 9 31 42 se va
afişa 17 31.

Si va rog sa-mi explicati cat de cat modul de functionare a programului..

Answer 1

Asta e un algortim pentru verificarea unui nr. prim:
bool CheckPrime(int Nr){
        bool IsPrime=true;
        if(Nr!=2){
                 if(Nr%2!=0){
                       for(int x=3;x<=sqrt((double)Nr);x+=2){
                                 if(Nr%x==0) IsPrime=false;
                       }
                       return IsPrime;
                 }else{
                        return false;
                  }
         }else{
             return true;
        }
}
Practic verficia daca numarul introdus e 2. Daca e 2 atunci e prim daca nu e 2 verifica daca e par. Daca e par atunci nu e prim (e par dar diferit de 2). Daca nu e nici 2 incepe intr-un for sa imparta numarul la toate numerele intre 3 si radicalul sau (vezi ca forul incrementeaza cu 2 nu cu 1-forfor(int x=3;x<=sqrt((double)Nr);x+=2) deoarece asa va sarii peste numere prime ,impartindu-l pe Nr la 3,5,7,9,..restul) Vezi ca trebuie radicalul sau. Deoarece odata ce ai trecut de radical stii deja la ce numere se imparte sau nu Nr.

Ex.: Nr=11*51=561. Radicalul sau e 23. Daca impartim pe Nr la toate nr. impare pana la 23:3,5,7,9,11,etc.. Vom vedea ca se imparte la 11 . Insa acum nici nu mai trebuie sa-l cautam pe 51 (stim ca se imparte la alt nr. decat 1 si el insusi).

Deci asta e un algoritm foarte eficient.

Cod:

ifstream fi("bac.in")

while(!fi.eof()){
   fi>>x;
   if(CheckPrime(x)) nrs[++count]=x;//array;count is integer=0
  if(count==2) break;
}
if(count==2) {
   cout<<nrs[0]<<" "<<nrs[1];
}else cout<<"Nr. insuficiente";