使用 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

您的除数约束不正确 - 您正在查看 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 的回答也以不同的方式解决了同样的问题。您的代码仍将检查不必要的除数。