Подсчет чисел в диапазоне [L, R] только с 2 или 7 в качестве простых множителей

Даны два целых числа L и R , задача состоит в том, чтобы найти количество чисел в диапазоне [L, R], которые имеют только 2 или 7 в качестве простых делителей .

Примеры:

Input: L = 0, R = 0
Output: 0 
Explanation: 0 is not divisible by 2 or 7

Input: L = 0, R = 2
Output: 1 
Explanation: Only 2 is the number between the range which has 2 as a factor, hence count is 1.

Input: L = 1, R = 15
Output: 5
Explanation: 2, 4, 7, 8 & 14 are the numbers which has factors as 2 or 7, hence, count is 5

Наивный подход: простой подход состоит в том, чтобы сгенерировать все простые множители каждого числа в диапазоне [L, R] и проверить, являются ли множители только 2 или 7.

Следуйте инструкциям, чтобы решить проблему:

• Переход от i = L к R :
  • Сохраните все простые факторы i в векторе (скажем, factor ).
  • Пройдите по вектору, чтобы увидеть, присутствуют ли факторы, отличные от 2 или 7 , или нет.
  • Если i делится только на 2 или 7 , то в противном случае увеличивается счетчик .
• Верните пару специальных и обычных в качестве окончательного ответа.

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

Сложность времени: О((П – Л) ^(3/2) )
Вспомогательное пространство: О (лог R)

Эффективный подход: проблема может быть решена более эффективно, если следовать упомянутому наблюдению:

Наблюдение:

Generate all the numbers of form 2*k or 7*k or 2*7*k using recursion where k is also in one of the previous three forms.

Следуйте инструкциям, чтобы решить проблему:

• Инициализируйте неупорядоченную карту как посещенную , чтобы сохранить уже посещенные числа, и подсчитайте как 0, чтобы сохранить количество таких чисел.
• Подготовьте рекурсивную функцию для генерации чисел, как показано в наблюдении.
• Если сгенерированное число (например, temp ):
  • В диапазоне [L, R] и еще не посещенном, затем отметьте его как посещенный и увеличьте count .
  • Превышает R или уже посещен, вернитесь из этой рекурсии и попробуйте другие варианты.
• Верните количество в качестве окончательного требуемого ответа.

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

Временная сложность: O(R)
Вспомогательное пространство: О(Р – Л)