Простой прямоугольник

Автор идеи: Демид Кучеренко Разработка задачи: Николай Ведерников

Для начала, давайте каждое простое число заменим на единицу, а каждое непростое на ноль, $$$a[i][j] = isPrime(a[i][j])$$$. Надо уметь проверять на простоту, за корень от числа. Теперь мы получили матрицу из нулей и единиц.

Далее, на полученной матрице из нулей и единиц, давайте посчитаем префиксные суммы, $$$sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + a[i][j]$$$. С помощью префиксных сумм мы сможем отвечать на количество единиц в прямоугольнике $$$(x1, y1), (x2, y2)$$$, $$$sum[x2 + 1][y2 + 1] + sum[x1][y1] - sum[x2 + 1][y1] - sum[x1][y2 + 1]$$$.

Последним шагом, давайте переберем левый верхний угол прямоугольник и правый нижний. Если количество единиц в этой матрице равен площади прямоугольника, то этот прямоугольник кандидат на ответ. Среди всех таких прямоугольников, выберем прямоугольник с наибольшей площадью.

Время работы: $$$O(n^2 * sqrt(10^6)$$$ — чтобы проверить каждое число на простоту, $$$O(n^2)$$$ — на построение префиксных сумм, а так же $$$O(n^4)$$$ — перебор углов прямоугольника. Итоговое время работы при $$$n = 100$$$ составляет $$$O(n^4)$$$.

Находить в матрице максимальный по площади прямоугольник из единиц можно и за время $$$O(n^2)$$$, но это не требовалось в этой задаче https://e-maxx.ru/algo/maximum_zero_submatrix