计算C中给定大范围内的完全平方数

Question

我已经有了计算 1 和最大范围之间的完全正方形数量的代码:

int perfectCounter = 0;
int i = 1;
int maxRange;

scanf("%d", &maxRange);

while (i <= maxRange) {
   float tempSquare = sqrt(i);
   int integerPart = tempSquare;

   if (tempSquare == integerPart)
      perfectCounter++;
}

问题是，最大范围必须在 1 到 10^1000 之间，所以我不能将 maxRange 存储在 int、long 或 long double 上。如果不使用处理非常大的数字的外部库，我想不出解决方案。

Answer 1

如果您只需要计算1..N 之间有多少个完全平方，您需要做的就是:对N 求平方根 并获取它的整数值:)

想想吧。对于 1..10 范围，正确答案是 3 (1, 4, 9) 顺便说一下，它是向下舍入的 sqrt(10)。如果您不想将 1 算作一个完美的正方形 - 好吧，不要算它。

一般来说，要查看 M..N 范围内有多少“完全正方形”，您需要做的就是:

(int)sqrt(N) - (int)sqrt(M) - 1

这应该很简单，因为您现在需要做的就是求出“非常大的数”的平方根。你必须为此编写一个函数，是的。但这并不太复杂，网络上有大量资源可以帮助您。