Проверить, может ли число быть представлено в виде суммы простого числа и полного квадрата

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

Учитывая положительное целое число N , задача состоит в том, чтобы проверить, может ли N быть представлено в виде суммы простого числа и полного квадрата или нет. Если возможно представить N в нужном виде, то выведите «Да» . В противном случае выведите «Нет» .

Примеры:

Input: N = 27
Output: Yes
Explanation: 27 can be expressed as sum of 2 (prime) and 25 (perfect square).

Input: N = 64
Output: No

Наивный подход: самый простой подход к решению данной проблемы — хранить все идеальные квадраты, которые меньше или равны N , в массиве. Для каждого идеального квадрата в массиве, скажем X , проверьте, является ли (N – X) простым числом или нет. Если найдено верно, то выведите «Да» . В противном случае выведите «Нет» .

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

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

Эффективный подход. Описанный выше подход можно оптимизировать, сохраняя все простые числа, меньшие N, в массиве с использованием решета Эратосфена. Если существует любое простое число, скажем X , проверьте, является ли (N – X) полным квадратом или нет. Если найдено верно, то выведите «Да» . В противном случае выведите «Нет» .

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

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

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