Найти разницу между количеством 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 , то это не простое число. Поэтому увеличивайте количество составных чисел.
- В противном случае увеличьте количество простых чисел.
- Перейдите от j = 2 к квадратному корню i .
- Верните разницу в качестве требуемого ответа.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O((RL) * sqrt(R))
Вспомогательное пространство: O(1)