Prime number product using Linq

Artikel
12/06/2007

Linq is SO FUN !!!

I have read this article from a french developer about Linq used to find the list of all the prime numbers < n : https://blogs.developpeur.org/raptorxp/archive/2007/11/26/quizz-linq-la-liste-des-nombres-premiers-en-3-clauses.aspx

Here is another sample: let's try to find the prime number product of an integer:

ex: 504 = 2 * 2 * 2 * 3 * 3 * 7

First step, let's find the first divider of an integer n, starting from 2. We just need to find the first integer which is dividing 'n' without rest value (source % i == 0). We are sure that the first divider 'd' is a prime number because all possible multiples of 'd' would have been detected before as a divider of the source. The following code will make that job.
```
 (from i in Enumerable.Range(2, source)
 where (source % i == 0) || (source == i)
 select i).First();
```

Once we have found a first prime divider we must iterate on the remaining value (source / divider) until source == 1

 while (source > 1)
{
    var divider =
        (from i in Enumerable.Range(2, source)
         where (source % i == 0) || (source == i)
         select i).First();
    source = source / divider;
}

I have chosen to expose the result through an enumeration of integers and as we are using C# 3.0, let's add this functionality to the 'int' class using method extensions.

 public static class IntExtensions
{
    public static IEnumerable<int> ToPrimeNumbersProduct(this int source)
    {
        while (source > 1)
        {
            var divider =
                (from i in Enumerable.Range(2, source)
                 where (source % i == 0) || (source == i)
                 select i).First();
            yield return divider;
            source = source / divider;
        }
    }
}

Now we are done, let's use it:

 foreach (var v in 144.ToPrimeNumbersProduct())
    Console.WriteLine(v);

Here is the output:

Most of the time we prefer to show it by grouping same dividers together powered to their count.

ex: 504 = 2^3 * 3^2 * 7

Once again Linq will allow us to make it very easilly, grouping the enumeration on the values themselves. Then each distinct divider will be the Key of the group and the power will be the count of that group.

 foreach (var v in
    (from i in 504.ToPrimeNumbersProduct()
     group i by i into g
     select new { Value = g.Key, Power = g.Count() })
     )
    Console.WriteLine(v);

Here is the output:

We can go a little bit further:

 var q =
    from i in 504.ToPrimeNumbersProduct()
    group i by i into g
    select g.Count() > 1 ?
             g.Key.ToString() + "^" + g.Count().ToString() :
             g.Key.ToString();
Console.WriteLine(string.Join(" * ", q.ToArray()));

Then the final output is:

Comments

Anonymous
December 06, 2007
PingBack from http://msdnrss.thecoderblogs.com/2007/12/06/prime-number-product-using-linq/
Anonymous
December 06, 2007
Actually, not stupid at all. Quite amazing, in fact. Check out this post on Mitsu's blog: Prime number
Anonymous
December 12, 2007
Optimisons un peu ça : public static IEnumerable<int> ToPrimeNumbersProduct(this int source) { while (source > 1 && source % 2 == 0) { yield return 2; source = source / 2; } int max = (int)Math.Sqrt(source); while (source > 1) { var divider = (from i in Enumerable.Range(2, max).Select(d => d * 2 - 1) where (source % i == 0) select i).First(); yield return divider; source = source / divider; } }
Anonymous
December 12, 2007
oups, there is a bug. public static IEnumerable<int> ToPrimeNumbersProduct(this int source) { while (source > 1 && source % 2 == 0) { yield return 2; source = source / 2; } int max = (int)Math.Sqrt(source); while (source > 1) { var divider = (from i in Enumerable.Range(2, max).Select(d => d * 2 - 1) where (source % i == 0) select i).FirstOrDefault(); if (divider == 0) divider = source; yield return divider; source = source / divider; } } is better
Anonymous
December 12, 2007
if I were not so stupid, it's should be better: public static IEnumerable<int> ToPrimeNumbersProduct2(this int source) { while (source % 2 == 0) { yield return 2; source = source / 2; } int max = (int)Math.Sqrt(source) / 2; while (source > 1) { var divider = (from i in Enumerable.Range(2, max).Select(d => d * 2 - 1) where (source % i == 0) select i).FirstOrDefault(); if (divider == 0) divider = source; yield return divider; source = source / divider; } }
Anonymous
July 29, 2008
Please follow the link below for new way of prime numbers http://kadiprimality.blogspot.com/
Anonymous
February 22, 2013
Please find best way write code. Func<int, IEnumerable<int>> primeNumbers = max => from i in Enumerable.Range(2, max - 1) where Enumerable.Range(2, i - 2).All(j => i % j != 0) select i; int source=15; var result = primeNumbers(source);

Delen via

Prime number product using Linq

Comments

Aanvullende resources