Найти разницу между количеством Prime и Composite в заданном диапазоне

Даны два целых числа L и R , задача состоит в том, чтобы найти значение (количество составных частей — количество простых чисел), которые лежат в диапазоне [L, R].

Примечание: 1 не считается ни простым, ни составным числом.

Примеры:

Input: L = 2, R = 10
Output: 1
Explanation: The composite numbers in the range are 4, 6, 8, 9, 10 and the prime numbers are 2, 3, 5, 7. So the output is 1.

Input: L = 4, R = 5
Output: 0

Подход: проблему можно решить, используя следующую идею:

Find the count of primes and the count of composites within the given range and then find the difference.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Переход от i = L к R :
  • Перейдите от j = 2 к квадратному корню i .
    • Если i делится на j , то это не простое число. Поэтому увеличивайте количество составных чисел.
    • В противном случае увеличьте количество простых чисел.
• Верните разницу в качестве требуемого ответа.

Ниже приведена реализация описанного выше подхода.

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