Необходимо найти количество чисел из диапазона (A, A+B] (A, B < 10^9), не содержащих простых делителей, меньших k (k < 300). Пробую перебирать произведения простых чисел, меньших k, и использовать формулу включения-исключения, примерно вот так:
int go(int count, int product, int prime_index)
{
if (product > B || prime_index == primes.size())
return 0;
int product_new = primes[prime_index] * product;
int count_new = count+1;
int result = 0;
if (count_new & 1)
{
result += (B / product_new - A / product_new);
}
else
{
result -= (B / product_new - A / product_new);
}
result += go(count+1, product_new, prime_index + 1);
result += go(count, product, prime_index + 1);
return result;
}
TL. Возможно ли как-нибудь ускорить данное решение или необходим другой подход? Спасибо.