Наибольшее целое число до N, имеющее наибольший простой делитель, превышающий его квадратный корень

Для заданного положительного целого числа N задача состоит в том, чтобы найти наибольшее число в диапазоне [1, N] такое, что квадратный корень числа меньше его наибольшего простого множителя.

Input: N = 15
Output: 15
Explanation: The prime factors of 15 are {3, 5}. The square root of 15 is 3.87 (i.e, 3.87 < 5). Therefore 15 is the largest valid integer in the given range.

Input: N = 25
Output: 23

Подход: Данную задачу можно решить, используя Решето Эратосфена с некоторыми модификациями. Создайте массив gpf[] , в котором хранится наибольший простой множитель всех целых чисел в заданном диапазоне. Изначально gpf[] = {0} . Используя Sieve, инициализируйте все индексы массива gpf[] наибольшим простым множителем соответствующего индекса аналогично алгоритму, обсуждаемому в этой статье.

Теперь выполните итерацию по диапазону [N, 1] в обратном порядке и выведите первое целое число, квадратный корень которого меньше его наибольшего простого множителя.

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

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