Проверить, может ли число быть представлено в виде суммы простого числа и полного квадрата
Учитывая положительное целое число 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)