Подсчитайте количество строк и столбцов в заданной матрице, имеющей все простые числа
Опубликовано: 20 Сентября, 2022
Учитывая двумерную матрицу arr[] размера N*M , задача состоит в том, чтобы найти количество строк и столбцов, содержащих все простые числа.
Примеры:
Input: arr[]= { { 2, 5, 7 }, { 3, 10, 4 }, { 11, 13, 17 } };
Output: 3
Explanation:
2 Rows: {2, 5, 7}, {11, 13, 17}
1 Column: {2, 3, 11}Input: arr[]={ { 1, 4 }, { 4, 6 } }
Output: 0
Подход: выполните следующие шаги, чтобы решить эту проблему:
- Примените алгоритм решета, чтобы найти все простые числа.
- Пройдите все элементы по строкам, чтобы найти количество строк, содержащих все простые числа.
- Примените вышеуказанный шаг для всех столбцов.
- Верните ответ в соответствии с приведенным выше наблюдением.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N*M)
Вспомогательное пространство: O(max(arr))