c# - 质数公式

Question

我正在尝试用 C# 编写素数函数，我想知道以下代码是否有效。它“似乎”适用于前 50 个左右的数字。我只是想确保无论数字有多大它都能正常工作:

static bool IsPrime(int number)
{
    if ((number == 2) || (number == 3) || (number == 5) || (number == 7) || (number == 9))
            return true;

    if ((number % 2 != 0) && (number % 3 != 0) && (number % 5 != 0) &&
        (number % 7 != 0) && (number % 9 != 0) && (number % 4 != 0) &&
        (number % 6 != 0))
        return true;

        return false;
 }

Answer 1

不，这是行不通的!例如，尝试 121 = 11 * 11，这显然不是质数。

对于提供给函数的任何数字，它是质数 X1, X2, ..., Xn(其中 n >= 2)与它们都大于或等于 11，您的函数将返回 true。 (而且，如前所述，9 不是质数)。

从维基百科可以看到:

In mathematics, a prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself.

所以一个非常简单和幼稚的检查数字是否为质数的算法可能是:

public bool CalcIsPrime(int number) {

    if (number == 1) return false;
    if (number == 2) return true;

    if (number % 2 == 0) return false; // Even number     

    for (int i = 2; i < number; i++) { // Advance from two to include correct calculation for '4'
       if (number % i == 0) return false;
    }

    return true;

}

要获得更好的算法，请查看此处:Primality Test

如果你想检查你的代码，做一个测试，这里是一个用xunit编写的测试用例.

        [Theory]
        [MemberData(nameof(PrimeNumberTestData))]
        public void CalcIsPrimeTest(int number, bool expected) {
            Assert.Equal(expected, CalcIsPrime(number));
        }

        public static IEnumerable<object[]> PrimeNumberTestData() {
            yield return new object[] { 0, false };
            yield return new object[] { 1, false };
            yield return new object[] { 2, true };
            yield return new object[] { 3, true };
            yield return new object[] { 4, false };
            yield return new object[] { 5, true };
            yield return new object[] { 6, false };
            yield return new object[] { 7, true };
            yield return new object[] { 8, false };
            yield return new object[] { 9, false };
            yield return new object[] { 10, false };
            yield return new object[] { 11, true };
            yield return new object[] { 23, true };
            yield return new object[] { 31, true };
            yield return new object[] { 571, true };
            yield return new object[] { 853, true };
            yield return new object[] { 854, false };
            yield return new object[] { 997, true };
            yield return new object[] { 999, false };
        }