LINQ Performance with SelectMany, GroupBy and First

If you tried the following code, the same problem will occur:

Enumerable.Range(1, 1000000000)
    .GroupBy(x => x)
    .First();

This means that all groups will be materialized during execution of the query, and that's the reason why OutOfMemoryException is thrown.

To solve the problem, you can use the following LINQ code as mentioned by @haim770 in the comments section:

Enumerable
    .Range(1, 1000000000)
    .First(i => Enumerable
        .Range(2, 19)
        .All(j => i % j == 0))

For more optimization, I found a better solution. Sorry for not using LINQ but it's much more optimized, maybe there's a way to achieve it using LINQ.

Instead of looping through a large amount of numbers and check each one, why not building the desired answer directly.

The desired output is a number x that is divisible by all numbers 1..n without any remainder. So, it is the multiple of all prime factors of numbers in range 1..n. by taking minimal amount of these prime factors, we can get the smallest number x.

For example, if n = 10 then:

i = 2: prime factors of 2 are [2] -> neededPrimes = [2]
i = 3: prime factors of 3 are [3] -> neededPrimes = [2, 3]
i = 4: prime factors of 4 are [2, 2] -> neededPrimes = [2, 2, 3] // we add just one 2 because the other already exists in neededPrimes
i = 5: prime factors of 5 are [5] -> neededPrimes = [2, 2, 3, 5]
i = 6: prime factors of 6 are [2, 3] -> neededPrimes = [2, 2, 3, 5] // we add nothing because [2, 3] are already in neededPrimes
i = 7: prime factors of 7 are [7] -> neededPrimes = [2, 2, 3, 5, 7]
i = 8: prime factors of 8 are [2, 2, 2] -> neededPrimes = [2, 2, 2, 3, 5, 7] // we add one 2 because the other 2's already exist in neededPrimes
i = 9: prime factors of 9 are [3, 3] -> neededPrimes = [2, 2, 2, 3, 3, 5, 7]
i = 10: prime factors of 10 are [2, 5] -> neededPrimes = [2, 2, 2, 3, 3, 5, 7]

x = 2 * 2 * 2 * 3 * 3 * 5 * 7 = 2520

Here's a code, and I hope it's clear:

public static void Main(string[] args)
{
    // The number to find its smallest multiple
    var n = 20;
    // A list that contains all primes that are founded across the calculation
    var calculatedPrimes = new List<int>();
    // Start through the numbers that x (the output number) should be divisible by
    for (var i = 2; i <= n; i++)
    {
        // Get primes of i
        var primes = GetPrimeFactors(i);
        // Loop through primes of i and add to "calculatedPrimes" the ones that are not 
        // in "calculatedPrimes"
        primes.ForEach(prime =>
        {
            if (!calculatedPrimes.Contains(prime) ||
                calculatedPrimes.Count(p => p == prime) < primes.Count(p => p == prime))
            {
                calculatedPrimes.Add(prime);
            }
        });
    }

    // The output number should be the multiple of all primes in "calculatedPrimes" list
    var x = calculatedPrimes.Aggregate(1, (res, p) => res * p);
    Console.WriteLine(x);

    Console.ReadLine();
}

// A function to get prime factors of a given number n
// (example: if n = 12 then this will return [2, 2, 3])
private static List<int> GetPrimeFactors(int n)
{
    var res = new List<int>();
    while (n % 2 == 0)
    {
        res.Add(2);
        n /= 2;
    }

    for (var i = 3; i <= Math.Sqrt(n); i += 2)
    { 
        while (n % i == 0)
        {
            res.Add(i);
            n /= i;
        }
    }

    if (n > 2)
        res.Add(n);
    return res;
}