使用 LINQ 的 C# 质数

Question

最近我对 LINQ 很感兴趣。我正在尝试获取质数。我实际上做得很好，但我的代码没有显示低于 Sqrt(n) 的素数。

static void Main(string[] args)
    {

        Func<int, int, IEnumerable<int>> EnumerableRange =
            (startPoint, endPoint) =>
                Enumerable.Range(Math.Min(startPoint, endPoint), Math.Abs(startPoint - endPoint) + 1);

        Func<int, int, bool> isFullyDivided =
            (value, divisor) =>
                (value % divisor).Equals(0);

        int sp = 2,
            ep = 100;

        var query =
            EnumerableRange(sp, ep)
            .Where(value =>
                EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(ep)))
                .Any(divisor =>
                    isFullyDivided(value, divisor))
                    );

        var primeNumbers =
            EnumerableRange(sp, ep)
            .Except(query);

        foreach (var item in primeNumbers)
        {
            Console
                .WriteLine(item);
        }

        Console
            .Read();

    }

目前，此代码不正确地遗漏了小于 sqrt(n) 的质数。该代码应该获取 2 到 100 之间的素数。相反，它只打印 11 及以上的素数。缺少素数 2, 3, 5, 7。

Answer 1

你逻辑有问题。一切都可以平分自己，所以你应该检查value != divisor。否则您将错误地排除将自身相除的数字（例如 5 % 5 == 0）。

var query =
    EnumerableRange(sp, ep)
    .Where(value =>
        EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(ep)))
        .Any(divisor =>
             value != divisor &&  //This is the logic you are missing
             isFullyDivided(value, divisor))
            );

Answer 2

您对除数的约束不正确 - 您正在查看 2 和 Sqrt(ep) (10) 之间的除数，而您只需要检查 2 和 Sqrt(value) 之间的除数：

    var query =
        EnumerableRange(sp, ep)
        .Where(value =>                                      V----------
            EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(value)))
            .Any(divisor =>
                isFullyDivided(value, divisor))
                );

这就是为什么你的质数从 11 开始，因为你的除数上升到 10，这将包括值本身。 @ryanyuyu 的回答也以不同的方式解决了同样的问题。您的代码仍将检查不必要的除数。

Answer 3

最佳解决方案：

            var query =
            EnumerableRange(sp, ep)
            .Where(value =>
                EnumerableRange(2, (int)Math.Ceiling(Math.Sqrt(value)))
                .Any(divisor =>
                    !value.Equals(divisor) &&
                    isFullyDivided(value, divisor))
                    );

Math.Floor 是错误的。正确的是 Math.Ceiling.

使用 LINQ 的 C# 质数

C# Prime Numbers with LINQ

c#

linq

lambda

primes