Найти группы в заданном диапазоне, имеющие не менее K последовательных составных целых чисел
Учитывая диапазон [L, R] и целое число K , найдите все группы в данном диапазоне, содержащие не менее K последовательных составных целых чисел.
Пример:
Input: L = 500, R = 650, K = 10
Output:
510 520 11
524 540 17
620 630 11
Explanation:
Prime number between 500 to 650 are
{503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647}.
So between them the consecutive composite number which are greater than K are 510-520, 524-540 and 620-630.Input: L = 10, R = 18, K = 2
Output:
14 16 3
Грубый подход: A простым решением было бы пройти все числа в заданном диапазоне и:
- Проверьте, является ли каждое число простым или нет.
- Ведите подсчет последовательных составных чисел.
- Выведите диапазон групп с их количеством, если значение превышает K .
Временная сложность: O((RL)*√R)
Вспомогательное пространство: O(1)
Эффективный подход: вместо поиска всех последовательных составных чисел мы можем использовать альтернативную гипотезу , чтобы найти простые числа в заданном диапазоне и эффективно решить проблему.
An efficient solution would be to use the Sieve of Eratosthenes to find the primes and check the range between them.
Выполните шаги, указанные ниже, чтобы реализовать описанный выше подход:
- Сгенерируйте простые числа между диапазоном.
- После создания массива простых чисел пройдитесь по массиву.
- Проверьте, есть ли последовательные составные числа больше 10.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность : O(R*log(log(R)))
Вспомогательное пространство : O(R)