Найдите простые числа в 2D-массиве (матрице)

Опубликовано: 20 Сентября, 2022

Учитывая двумерный массив mat[][] , задача состоит в том, чтобы найти и напечатать простые числа вместе с их положением (индексация на основе 1) в этом двумерном массиве.

Примеры:

Input: mat[][] = {{1, 2}, {2, 1}}  

Output: 

1 2 2

2 1 2

Explanation:  First prime is at position row 1 and column 2 and the value is 2

Second prime is at position row 2 and column 1 and the value is 2

Input: mat[][] = {{1, 1}, {1, 1}}  

Output: -1

Explanation:  There is no prime number in this 2d array

Наивный подход: основная идея состоит в том, чтобы пройти по двумерному массиву и для каждого числа проверить, является ли оно простым или нет. Если оно простое, выведите позицию и значение для каждого найденного простого числа.
Временная сложность: O(NM*sqrt(X)), где N*M — размер матрицы, а X — самый большой элемент в матрице.
Вспомогательное пространство: O(1)

Эффективный подход: мы можем эффективно проверить, является ли число простым или нет, используя сито. Затем пройдите по массиву 2d и просто проверьте, является ли число простым или нет в O (1).

Выполните следующие шаги для реализации этого подхода:

  • Найдите максимальный элемент матрицы и сохраните его в переменной maxNum .
  • Теперь найдите простые числа от 1 до maxNum, используя решето Эратосфена. и сохраните результат в массиве prime[] .
  • Теперь пройдитесь по матрице и для каждого числа проверьте, является ли оно простым или нет, используя массив Prime[] .
  • Для каждого простого числа в матрице выведите его позицию (строку, столбец) и значение.

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


Временная сложность: O(N*M), где N*M — размер матрицы.
Вспомогательное пространство: O(maxNum), где maxNum — самый большой элемент в матрице.

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