素数公式

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不是素数).

从维基百科您可以看到:

在数学中,素数(或素数)是一个自然数,它具有两个截然不同的自然数除数:1和它本身.

因此,检查数字是否为素数的一个非常简单和天真的算法可能是:

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 };
        }

Answer 2

这必须要完成...

public static bool IsPrime(this int number)
{
    return (Enumerable.Range(1,number).Where(x => number % x == 0).Count() == 2);
}