Есть ли какой-нибудь быстрый способ в C (менее 1 сек), чтобы найти число совершенных квадратов между двумя числами. Напр. для 1 ↔ 10 мы имеем 2 совершенных квадрата 4 и 9. Но что между 1 ↔ 2 ^ 60 или некоторым другим большим числом.
Это медленное
while(i*i<=n)
{
sum+=i==((long long)(sqrt(i*i)));
i++;
}
где n означает 2 ^ 60, и мы начинаем с я = 2.
x = (int)sqrt(n2) - (int)sqrt(n1);
Его тривиально. Предположим, что у вас есть две конечные точки: a и b, б.
Какая следующая идеальная площадь после? Подсказка: что такое sqrt (a)? Что будет делать округление?
Каков самый большой идеальный квадрат, который не превышает b? Подсказка: что такое sqrt (b)? Опять же, как бы помощь округления здесь?
Как только вы знаете эти два числа, подсчет числа совершенных квадратов кажется действительно тривиальным.
Кстати, будьте осторожны. Даже sqrt 2 ^ 60 - большое количество, хотя он будет вписываться в двойной. Проблема в том, что 2 ^ 60 слишком велика, чтобы вписаться в стандартный двойник, так как она превышает 2 ^ 53. Поэтому будьте осторожны с проблемами точности.
Не перебирайте. Уравнение:
floor(sqrt(b)) - ceil(sqrt(a)) + 1
дает число совершенных квадратов в интервале от a до b включительно.
if(n1 is a perfect square)
x=(int)sqrt(n2)-(int)sqrt(n1)+1;
else
x=(int)sqrt(n2)-(int)sqrt(n1);