通过限制迭代次数来查找数字是否为Prime？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没有这样的技巧