Prime number product using Linq

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

1. 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();
   

2. 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;
   }
   

3. 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);