c# - 通过限制迭代次数判断一个数是否为素数-c#

Question

我想通过尽可能限制迭代次数来确定一个数字是否为质数。以下程序是博客中建议的。我可以理解这部分代码..

public static bool Isprime(long i)
    {
        if (i == 1)
        {
            return false;
        }
        else if (i < 4)
        {
            return true;
        }
        else if (i % 2 == 0)
        {
            return false;
        }
        else if (i < 9)
        {
            return true;
        }
        else if (i % 3 == 0)
        {
            return false;
        }

但是我不明白为什么f会增加6。

else
        {
            double r = Math.Floor(Math.Sqrt(i));
            int f = 5;
            while (f <= r)
            {
                if (i % f == 0) { return false; }
                if (i % (f + 2) == 0) { return false; }
                f = f + 6;
            }
            return true;
        }  
    }

Answer 1

因为每个素数(除了 2 和 3)都是 6k +/- 1 的形式每隔一个数字都不能是质数，因为它们可以被 2 或 3 整除另外，对您的方法进行一些修改:

public static bool Isprime(long i)
{
    if (i < 2)
    {
        return false;
    }
    else if (i < 4)
    {
        return true;
    }
    else if ((i & 1) == 0)
    {
        return false;
    }
    else if (i < 9)
    {
        return true;
    }
    else if (i % 3 == 0)
    {
        return false;
    }
    else
    {
        double r = Math.Floor(Math.Sqrt(i));
        int f = 5;
        while (f <= r)
        {
            if (i % f == 0) { return false; }
            if (i % (f + 2) == 0) { return false; }
            f = f + 6;
        }
        return true;
    }  
}

• 你没有检查负数
• 要检查数字是否为偶数，(i & 1) == 0 更有效。不幸的是，i % 3 没有这样的技巧