#1495 pbinfo
Cerința
Se dă o matrice cu m linii şi n coloane, având elementele numere naturale nenule. Parcurgând matricea pe coloane de sus în jos şi de la stânga la dreapta, determinaţi lungimea maximă a unei secvenţe de numere prime.
Date de intrare
Fișierul de intrare memory004.in conține pe prima linie numerele m şi n, iar pe următoarele m linii câte n numere naturale, separate prin spații, reprezentând elementele matricei.
Date de ieșire
Fișierul de ieșire memory004.out va conține pe prima linie numărul L, reprezentând lungimea maximă a unei secvenţe de numere prime din matrice obţinută prin parcurgerea matricei pe coloane, de sus în jos şi de la stânga la dreapta.
Restricții și precizări
2 ≤ m , n ≤ 1000
elementele matricei sunt numere naturale mai mici decât 10.000
Exemplu
memory004.in
3 4
1 6 5 11
2 4 3 9
2 4 7 8
memory004.out
4
Răspunsuri la întrebare
Răspuns:
#include <bits/stdc++.h>
int prime(int n)
{
if (n == 1)
return 0;
if (n == 2 || n == 3)
return 1;
int flag = 0;
for (int i = 2; i <= n / 2; i++)
if (n % i == 0)
{
flag = 1;
break;
}
if (flag)
return 0;
return 1;
}
using namespace std;
int main()
{
int m, n;
cin >> m >> n;
int a[m][n];
int maxi = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
for (int i = 0; i < m; i++)
{
int num = 0;
for (int j = 0; j < n; j++)
{
if (prime(a[i][j]) == 1)
num++;
}
if (num > maxi)
maxi = num;
}
for (int i = 0; i < n; i++)
{
int num = 0;
for (int j = 0; j < m; j++)
{
if (prime(a[i][j]) == 1)
num++;
}
if (num > maxi)
maxi = num;
}
cout << maxi;
return 0;
}
Explicație:
folosim un algoritm foarte complex pentru a rezolva problema