为了记录在案，另一种方法是使用素分解。如果分解的每个因子都是偶数，那么这个数就是一个完美的平方。所以你想要的是看看一个数是否可以分解成质数平方的乘积。当然，你不需要获得这样的分解，只是为了看看它是否存在。

首先建立一个小于2^32的素数平方表。这远远小于一个包含所有整数的表，直到这个极限。

解决方案如下：

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

我想这有点神秘。它所做的是在每一步中检查质数的平方除以输入数。如果这样做了，那么它将尽可能地将数字除以平方，以从素数分解中删除这个平方。如果通过这个过程，我们得到1，那么输入数是素数平方的分解。如果平方比数字本身大，那么这个平方或任何更大的平方都无法分割它，所以数字不能是素数平方的分解。

考虑到现在的sqrt是在硬件中完成的，并且需要在这里计算素数，我想这个解决方案要慢得多。但正如mrzl在他的回答中所说，它应该比sqrt的解决方案给出更好的结果，sqrt的工作时间不会超过2^54。

我参加聚会已经很晚了，但我希望能提供一个更好的答案；更短，（假设我的基准是正确的）也更快。

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
    // Each square ends with an even number of zeros.
    if ((numberOfTrailingZeros & 1) != 0) return false;
    x >>= numberOfTrailingZeros;
    // Now x is either 0 or odd.
    // In binary each odd square ends with 001.
    // Postpone the sign test until now; handle zero in the branch.
    if ((x&7) != 1 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

第一个测试很快捕捉到大多数非正方形。它使用一个长的64项表，因此没有数组访问成本（间接和边界检查）。对于均匀随机的长，有81.25%的概率在这里结束。

第二个测试捕获因式分解中奇数为2的所有数字。Long.numberOfTrailingZeros方法非常快，因为它被JIT编译成一条i86指令。

删除尾随零后，第三个测试处理以二进制形式的011、101或111结尾的数字，这些数字不是完美的正方形。它还关心负数，也处理0。

最后的测试是双倍算术。由于double只有53位尾数，从long到double的转换包括大值的舍入。尽管如此，测试是正确的（除非证明是错误的）。

试图结合mod255的想法并不成功。

整数牛顿法

如果希望避免非整数运算，可以使用以下方法。它基本上使用了为整数运算而修改的牛顿法。

/**
 * Test if the given number is a perfect square.
 * @param n Must be greater than 0 and less
 *    than Long.MAX_VALUE.
 * @return <code>true</code> if n is a perfect
 *    square, or <code>false</code> otherwise.
 */
public static boolean isSquare(long n)
{
    long x1 = n;
    long x2 = 1L;

    while (x1 > x2)
    {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }

    return x1 == x2 && n % x1 == 0L;
}

此实现无法与使用Math.sqrt的解决方案竞争。但是，可以通过使用其他文章中描述的过滤机制来提高其性能。

你必须做一些基准测试。最佳算法将取决于输入的分布。

您的算法可能接近最佳，但在调用平方根例程之前，您可能需要快速检查以排除某些可能性。例如，通过按位“和”查看十六进制数字的最后一位。完美的正方形只能以0、1、4或9结尾，以16为底。因此，对于75%的输入（假设它们是均匀分布的），可以避免调用平方根，以换取一些非常快的位旋转。

Kip对实现十六进制技巧的以下代码进行了基准测试。当测试数字1到100000000时，此代码的运行速度是原始代码的两倍。

public final static boolean isPerfectSquare(long n)
{
    if (n < 0)
        return false;

    switch((int)(n & 0xF))
    {
    case 0: case 1: case 4: case 9:
        long tst = (long)Math.sqrt(n);
        return tst*tst == n;

    default:
        return false;
    }
}

当我在C++中测试类似的代码时，它实际上比原始代码运行得慢。然而，当我消除switch语句时，十六进制技巧再次使代码速度提高了一倍。

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

消除switch语句对C#代码几乎没有影响。

如果最后的X位数字是N，那么应该可以更有效地包装“不能是完美的正方形”！我将使用java 32位int，并生成足够的数据来检查数字的最后16位，即2048个十六进制int值。

...

好吧。要么我遇到了一些超出我理解范围的数论，要么我的代码中有一个错误。无论如何，以下是代码：

public static void main(String[] args) {
    final int BITS = 16;

    BitSet foo = new BitSet();

    for(int i = 0; i< (1<<BITS); i++) {
        int sq = (i*i);
        sq = sq & ((1<<BITS)-1);
        foo.set(sq);
    }

    System.out.println("int[] mayBeASquare = {");

    for(int i = 0; i< 1<<(BITS-5); i++) {
        int kk = 0;
        for(int j = 0; j<32; j++) {
            if(foo.get((i << 5) | j)) {
                kk |= 1<<j;
            }
        }
        System.out.print("0x" + Integer.toHexString(kk) + ", ");
        if(i%8 == 7) System.out.println();
    }
    System.out.println("};");
}

结果如下：

（ed：由于pretify.js性能不佳而取消；查看修订历史以查看。）

不知道最快，但最简单的方法是以正常方式取平方根，将结果乘以自身，看看它是否与原始值匹配。

由于我们在这里讨论的是整数，fasted可能涉及一个集合，您可以在其中进行查找。