如何修复将9、25和49列为质数的算法

Question

如果数字是质数或非质数，此方法将返回true或false。问题是它将9，25和49显示为质数。我怎么才能修复它？

public static bool IsItPrime(int prime)
{
    if (prime == 2)
        return true;
    else if (prime < 2 || prime % 2 == 0)
        return false;
    else
    {
        int limit = (int)Math.Sqrt(prime);
        for (int i = 2; i < limit; i++)
        {
            if (prime % i == 0)
                return false;                    
        }
    }
    return true;
}

Answer 1

将内部循环从

for (int i = 2; i < limit; i++)

至

for (int i = 2; i <= limit; i++)

你遗漏的所有值都是相应奇数的平方- 3，5，7等等。如果你把(int)Math.Sqrt(prime)作为一个限制，那么你也应该检查这个限制。

Answer 2

在循环中使用<=而不是<。不正确的数字是平方，唯一的其他因素是平方根--但是使用<，您永远不会达到平方根。