Question

Va rog, un algoritm in c++ Nu prea stiu Ciurul lui Erastotene
Cerinţa
Se dau n numere naturale mai mici decât 1.000.000. Determinaţi câte dintre ele sunt prime.

Date de intrare
Fişierul de intrare eratostene.in conţine pe prima linie numărul n; urmează cele n numere, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieşire
Fişierul de ieşire eratostene.out va conţine pe prima linie numărul C, reprezentând numărul valorilor citite care erau numere prime.

Restricţii şi precizări
1 ≤ n ≤ 1.000.000



Exemplu
eratostene.in

6
12 18 19 25 29 7
eratostene.out

3

Answer 1

Problema nu iti spune ca trebuie sa folosesti neaparat ciurul lui Eratostene(care e de asemenea simplu). La acest ciur practic iei un numar prim(primul nr. prim) adica 2 si ii aflii multiplii pana la o limita adica 2*2,2*3,2*4 ....apoi ii elimini din sirul (array-ul) 1,2,3,4,...,n .Apoi iei urmatorul nr. care nu a fost eliminat din sir adica 3 si ii aflii din nou multiplii si ii elimini...Insa poti folosii o metoda mai simpla. O functie pe care am scris-o super rapida pentru acest lucru:

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;
        }
}

Acesta e tot codul:

#include <iostream>
#include<math.h>  //Trebuie neaparat sa o incluzi
#include <fstream>

using namespace std;

bool CheckPrime(int Nr);

int main(){
     ifstream fin("eratostene.in");
     ofstream fout("erastotene.out");
     int n=0,nr=0,count=0;

     fin>>n;
     for(int x=1;x<=n;x++){
          fin>>nr;
          if(CheckPrime(nr)==true) count=count+1;
     }

     fout<<count;
     fin.close();
     fout.close();

     return 0;
}

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;
        }