CODEWITHSUNDEEP
c#linqlambdaprimes
Artxzta
Artxzta

Reputation: 117

C# Prime Numbers with LINQ

I am interested with LINQ these days. I am trying to get prime numbers. I am actually did very well but my code doesn't show primes which is below 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();

    }

Currently, this code incorrect leaves out the prime numbers that are less than sqrt(n). The code is supposed to get the primes between 2 and 100. Instead it only prints prime numbers 11 and above. The primes 2, 3, 5, 7 are missing.

Upvotes: 2

Views: 1898

Answers (3)

Artxzta
Artxzta

Reputation: 117

Best solution :

            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 is wrong. Correct one is Math.Ceiling.

Upvotes: 0

D Stanley
D Stanley

Reputation: 152521

You constraint of divisors is incorrect - you are looking at divisors between 2 and Sqrt(ep) (10), when you only need to check divisors between 2 and Sqrt(value):

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

That is why your primes start at 11, because your divisors go up to 10 which would include the value itself. @ryanyuyu's answer also solves the same problem but in a different way. Your code will still be checking unnecessary divisors.

Upvotes: 2

ryanyuyu
ryanyuyu

Reputation: 6486

You have a logic problem. Everything can evenly divide itself, so you should check that the value != divisor. Otherwise you will incorrectly exclude the numbers that divide themselves (for example 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))
            );

Upvotes: 2

Related Questions