Максимизируйте размер подмножества из значений матрицы, чтобы любая пара была взаимно простой

Имея два целых числа N и M , обозначающие матрицу размера N*M , в которой значение каждой ячейки равно сумме номера строки и номера столбца, задача состоит в том, чтобы найти максимальный размер подмножества, которое может быть сформировано с помощью элементы этой матрицы такие, что любая пара из подмножества будет взаимно проста.

Примеры:

Input: N = 3, M = 4
Output: 4
Explanation: There are a maximum of 4 possible numbers on the matrix, Which are: {2, 5, 7, 3}, This makes pairs with the combination itself and has the GCD of that pair equal to one. i, e. (2, 3), (2, 5), (5, 3) . . . The matrix is shown below

2	3	4	5
3	4	5	6
4	5	6	7

Input: N = 5, M = 8
Output: 6

Подход: Задача может быть решена на основе следующего наблюдения.

As any pair of the subset will be coprime to each other, therefore the subset will be formed using all the prime within the range [2, N+M].

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте функцию, которая проверяет, является ли число простым.
• Запустите цикл от i = 2 до N+M .
  • Проверить, является ли текущее число простым или нет.
    • Если да, то увеличьте переменную счетчика.
• Наконец, верните количество простых чисел в качестве ответа.

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

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

Статьи по Теме:

• Простые числа
• Введение в матрицу или сетку - учебник по структуре данных и алгоритмам