Идеальные квадраты между двумя номерами

Question

Есть ли какой-нибудь быстрый способ в C (менее 1 секунды), чтобы найти число идеальных квадратов между двумя числами. Для примера. для 1 < -> 10 у нас есть 2 идеальных квадрата 4 и 9. Но как насчет между 1 < -> 2^60 или некоторым другим большим числом.

Это медленно

while(i*i<=n) 
{ 
    sum+=i==((long long)(sqrt(i*i))); 
    i++; 
} 

где п позволяет сказать, что 2^60, и мы начинаем с г = 2.

Answer 1

x = (int)sqrt(n2) - (int)sqrt(n1); 

Answer 2

Его тривиально. Предположим, у вас есть две конечные точки: & b, с < b.

1. Какая следующая идеальная площадь после? Подсказка: что такое sqrt (a)? Что бы округлить?

2. Что представляет собой самый большой идеальный квадрат, который не превышает b? Подсказка: что такое sqrt (b)? Опять же, как бы округлить помощь здесь?

Как только вы знаете эти два числа, подсчет количества идеальных квадратов кажется действительно тривиальным.

Кстати, будьте осторожны. Даже sqrt 2^60 - большое количество, хотя он будет вписываться в двойной. Проблема в том, что 2^60 слишком велика, чтобы вписаться в стандартный двойник, так как она превышает 2^53. Поэтому будьте осторожны с проблемами точности.

Answer 3

if(n1 is a perfect square)  
    x=(int)sqrt(n2)-(int)sqrt(n1)+1; 
else 
    x=(int)sqrt(n2)-(int)sqrt(n1); 

Answer 4

Не перебирайте. Уравнение:

floor(sqrt(b)) - ceil(sqrt(a)) + 1 

дает число совершенных квадратов в интервале от a до b включительно.

https://en.wikipedia.org/wiki/Intermediate_value_theorem