Подсчитайте количество строк и столбцов в заданной матрице, имеющей все простые числа

Опубликовано: 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

Подход: выполните следующие шаги, чтобы решить эту проблему:

  1. Примените алгоритм решета, чтобы найти все простые числа.
  2. Пройдите все элементы по строкам, чтобы найти количество строк, содержащих все простые числа.
  3. Примените вышеуказанный шаг для всех столбцов.
  4. Верните ответ в соответствии с приведенным выше наблюдением.

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N*M)
Вспомогательное пространство: O(max(arr))

РЕКОМЕНДУЕМЫЕ СТАТЬИ