# 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 : http://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.

2. ```(from i in Enumerable.Range(2, source)
where (source % i == 0) || (source == i)
select i).First();```

3. Once we have found a first prime divider we must iterate on the remaining value (source / divider) until source == 1
4. ```while (source > 1)
{
var divider =
(from i in Enumerable.Range(2, source)
where (source % i == 0) || (source == i)
select i).First();
source = source / divider;
}```
5. 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.
6. ```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: Tags

Comments (7)
1. MSDN Blog Postings » Prime number product using Linq says:
2. Mabsterama says:

Actually, not stupid at all. Quite amazing, in fact. Check out this post on Mitsu’s blog: Prime number

3. Matthieu MEZIL says:

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;

}

}

4. Matthieu MEZIL says:

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

5. Matthieu MEZIL says:

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;

}

}

6. Kadhirvel says:

Please follow the link below for new way of prime numbers

http://kadiprimality.blogspot.com/

7. Paresh Desai says:

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

Skip to main content