Question

Problema #303 eratostene de pe pbinfo in c++ va rog:
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

Răspuns:

Explicație:

#include <iostream>

#include <fstream>

using namespace std;

int a[1000001], b[1000001];

int main()

{

  ifstream f("eratostene.in");

  ofstream g("eratostene.out");

  int n, i, j, nrp=0, m=1000000;

  f>>n;

  for (i=1; i<=n; ++i) f>>b[i];

   for (i = 2; i <= m; i++)

       a[i] = 1;

   for (i = 2; i*i <= m; i++)

       if (a[i]!=0)

           for (j = 2; j <= m / i; j++)

               a[i*j] = 0;

   

   for (i = 1; i <= n; i++)

       if (a[b[i]] == 1) ++nrp;

   g << nrp;

   return 0;

}