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

Есть ли какой-нибудь быстрый способ в 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.

Ответы

Ответ 1

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

Ответ 2

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

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

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

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

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

Ответ 4

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