Question

#667 NrPrime1

Cerința
Se dă o matrice cu n linii și m coloane și elemente numere naturale. Să se determine câte dintre elementele situate pe coloane cu indici impari sunt prime.

Date de intrare
Programul citește de la tastatură numerele n m, iar apoi n șiruri cu câte m numere naturale, reprezentând elementele matricei.

Date de ieșire
Programul va afișa pe ecran numărul C, reprezentând valoarea căutată.

Restricții și precizări
1 ≤ n , m ≤ 600
elementele matricei sunt numere naturale mai mici decât 1.000.000
liniile matricei sunt numerotate de 1 la n, iar coloanele de la 1 la m



Exemplu
Intrare

4 3
5 2 10
3 9 1
7 10 1
10 19 3
Ieșire

4
Explicație
Cele 4 valori prime determinate sunt cele evidențiate mai jos:

5 2 10
3 9 1
7 10 1
10 19 3
Observăm că matricea conține și alte elemente prime, dar ele nu sunt situate pe coloane cu indici impari.

Answer 1

#include <iostream>

using namespace std;

char ciur[1000000];

int main(){

   int n, m, nr = 0, i, j, k;

   cin >> n >> m;

   ciur[1] = ciur[0] = 1;

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

       if (ciur[i] == 0)

        for (j = i*i;j <= 1000000;j += i)

         ciur[j] = 1;

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

       for (j = 1;j <= m;j++){

        cin >> k;

        if (j%2 == 1 && ciur[k] == 0)

               nr++;

    }

   cout << nr;

   return 0;

}