Share via


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:

image

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:

image

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:

image

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