Timus 1940

Необходимо найти количество чисел из диапазона (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. Возможно ли как-нибудь ускорить данное решение или необходим другой подход? Спасибо.