"factors of" method

[John A Grandy]

Does .NET provide a "factors of" method ?

I need to determine the factors of an integer.

[Jon Skeet [C# MVP]]

<"John A Grandy" <johnagrandy-at-gmail-dot-com>wrote:

Does .NET provide a "factors of" method ?

No.

I need to determine the factors of an integer.

You'll need to use the standard algorithms to find them, I'm afraid.
How big might these integers get?

--
Jon Skeet - <sk***@pobox.com>
Web site: http://www.pobox.com/~skeet
Blog: http://www.msmvps.com/jon.skeet
C# in Depth: http://csharpindepth.com

[Peter Morris]

Try something like this

public List<intFactorsOf(int value)
{
List<intresult = new List<int>();
List<intprimeNumbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prime);
value = value / prime;
}
}

return result;
}
Might not work or even compile :-)

Pete

[Jeroen Mostert]

Peter Morris wrote:

Try something like this

public List<intFactorsOf(int value)
{
List<intresult = new List<int>();
List<intprimeNumbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prime);
value = value / prime;
}
}

return result;
}
Might not work or even compile :-)

It'll work (in the sense that it produces unique prime factors, if you've
typed out the list correctly), but it's preposterously inefficient for most
numbers. Try value == 4 to see what I mean. It's easy enough to fix, though;
you need to replace one keyword with another. The resulting list will be
slightly different.

If you're going for the brute force approach, though, there's no particular
reason to use a list of primes. Just divide by every number from 2 upwards;
only the primes will actually come out as factors.

--
J.

[John A Grandy]

Hmmm ... perhaps I mis-used the word "factor" ....

I'm not just interested in prime factors , but all factors.

Brute force is easy, but perhaps a better algorithm exists.
public static List<intFindFactors( int number, int maxFactors )
{
List<intfactors = new List<int>( maxFactors );

factors.Add( 1 );

for ( int i = 2; i < number / 2 + 1; i++ )
{
if ( ( number % i ) == 0 )
{
factors.Add( i ) ;

if ( factors.Count >= maxFactors )
{
break;
}
}
}

return factors;
}
"Jeroen Mostert" <jm******@xs4all.nlwrote in message
news:48*********************@news.xs4all.nl...

Peter Morris wrote:

>Try something like this

public List<intFactorsOf(int value)
{
List<intresult = new List<int>();
List<intprimeNumbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prime);
value = value / prime;
}
}

return result;
}
Might not work or even compile :-)

It'll work (in the sense that it produces unique prime factors, if you've
typed out the list correctly), but it's preposterously inefficient for
most numbers. Try value == 4 to see what I mean. It's easy enough to fix,
though; you need to replace one keyword with another. The resulting list
will be slightly different.

If you're going for the brute force approach, though, there's no
particular reason to use a list of primes. Just divide by every number
from 2 upwards; only the primes will actually come out as factors.

--
J.

[Family Tree Mike]

Actually 2 upwards to n / 2 would be sufficient.

"Jeroen Mostert" <jm******@xs4all.nlwrote in message
news:48*********************@news.xs4all.nl...

If you're going for the brute force approach, though, there's no
particular reason to use a list of primes. Just divide by every number
from 2 upwards; only the primes will actually come out as factors.

--
J.

[Brian Gideon]

On Aug 19, 3:03*pm, "John A Grandy" <johnagrandy-at-gmail-dot-com>
wrote:

Does .NET provide a "factors of" method ?

I need to determine the factors of an integer.

Ah...the holy grail of computing!

How big are the numbers you're wanting to factor?

Browse through this wikipedia article. It gives a brief overview of
several algorithms.

http://en.wikipedia.org/wiki/Integer_factorization

[K Viltersten]

Actually 2 upwards to n/2 would be sufficient.

I think up to the square root is enough as
well, while being faster for most cases.

--
Regards
Konrad Viltersten
----------------------------------------
May all spammers die an agonizing death;
have no burial places; their souls be
chased by demons in Gehenna from one room
to another for all eternity and beyond.

[K Viltersten]

If you know how to get PRIME factors, you
only need to loop through them and multiply
them pairwise in all permutations.

I suspect that what you'd like to see is,
in fact, a list of vectors such that all
elements of one multiplied equal to the
original number you wanted to factorize.
Have i nailed it?

E.g., for 180 you need to have (i guess)
2 * 2 * 3 * 3 * 5 (prime factors)
but also
4 * 3 * 3 * 5
2 * 6 * 3 * 5
2 * 3 * 3 * 10
2 * 2 * 9 * 5
2 * 2 * 3 * 15
12 * 3 * 5
3 * 3 * 20
2 * 18 * 5
2 * 2 * 45
2 * 3 * 30
3 * 60
2 * 90
36 * 5
I might have missed a few possibilities,
of course, but this is the general idea
of what i SUSPECT you'd like to get.

--
Regards
Konrad Viltersten
----------------------------------------
May all spammers die an agonizing death;
have no burial places; their souls be
chased by demons in Gehenna from one room
to another for all eternity and beyond.
"John A Grandy" <johnagrandy-at-gmail-dot-comskrev i meddelandet
news:OR**************@TK2MSFTNGP02.phx.gbl...

Hmmm ... perhaps I mis-used the word "factor" ....

I'm not just interested in prime factors , but all factors.

Brute force is easy, but perhaps a better algorithm exists.
public static List<intFindFactors( int number, int maxFactors )
{
List<intfactors = new List<int>( maxFactors );

factors.Add( 1 );

for ( int i = 2; i < number / 2 + 1; i++ )
{
if ( ( number % i ) == 0 )
{
factors.Add( i ) ;

if ( factors.Count >= maxFactors )
{
break;
}
}
}

return factors;
}
"Jeroen Mostert" <jm******@xs4all.nlwrote in message
news:48*********************@news.xs4all.nl...

>Peter Morris wrote:

>>Try something like this

public List<intFactorsOf(int value)
{
List<intresult = new List<int>();
List<intprimeNumbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prime);
value = value / prime;
}
}

return result;
}
Might not work or even compile :-)

It'll work (in the sense that it produces unique prime factors, if you've
typed out the list correctly), but it's preposterously inefficient for
most numbers. Try value == 4 to see what I mean. It's easy enough to fix,
though; you need to replace one keyword with another. The resulting list
will be slightly different.

If you're going for the brute force approach, though, there's no
particular reason to use a list of primes. Just divide by every number
from 2 upwards; only the primes will actually come out as factors.

--
J.

[Peter Morris]

but it's preposterously inefficient

Try value == 4 to see what I mean. It's easy enough to fix, though; you
need to replace one keyword with another.

Maybe you should reveal the keyword?

If you're going for the brute force approach, though, there's no
particular reason to use a list of primes. Just divide by every number
from 2 upwards;

I could, but that would be preposterously inefficient :-)

[Peter Morris]

Probably a better way to do it than this, but it works
Dictionary<int, intresult = new Dictionary<int,int>();

int sourceValue = 4096;
int lowValue = 1;
int highValue = sourceValue;

while (lowValue <= highValue)
{
int newHighValue = highValue;
while (newHighValue >= lowValue)
{
if (newHighValue * lowValue == sourceValue)
{
result[lowValue] = newHighValue;
highValue = newHighValue - 1;
break;
}
newHighValue--;
}

lowValue++;
}

foreach (KeyValuePair<int, intkvp in result)
Console.WriteLine("{0} x {1}", kvp.Key, kvp.Value);
Console.ReadLine();
Pete

[K Viltersten]

Probably a better way to do it than this, but it works.

Dictionary<int, intresult;

We don't know (yet) what OP ment but
intuitively i'd lke to find more than
*pairs* the product of which equals to
the original number.

{2, 3, 5} -30

--
Regards
Konrad Viltersten
----------------------------------------
May all spammers die an agonizing death;
have no burial places; their souls be
chased by demons in Gehenna from one room
to another for all eternity and beyond.

[Peter Morris]

Try this. I am not sure if the output is correct or not but at first glance
it looks okay. Should at least give you a good start, I hope.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
Dictionary<int, intresult = new Dictionary<int, int>();

int sourceValue = int.MaxValue;
int lowValue = 1;
int highValue = sourceValue;

while (lowValue <= highValue)
{
highValue = FindHighestFactor(lowValue, highValue, sourceValue);

if (highValue * lowValue == sourceValue)
{
result[lowValue] = highValue;
highValue--;
}

lowValue++;
if (lowValue % 50 == 0)
Console.WriteLine("Processing {0}", lowValue);
}

foreach (KeyValuePair<int, intkvp in result)
Console.WriteLine("{0} x {1}", kvp.Key, kvp.Value);
Console.ReadLine();

}

private static int FindHighestFactor(int lowValue, int highValue, int
sourceValue)
{
int currentProduct = lowValue * highValue;
int difference = sourceValue - currentProduct;
if (difference == 0)
return highValue;
return highValue + (int)Math.Ceiling((double)difference / lowValue);

}
}
}

[Peter Morris]

Those are all prime factors of the source. He seems to have wanted all
factors (e.g. for solving quadratic equasions).

[Peter Morris]

Check my other post, it's a faster approach that doesn't seem to work at a
constant speed.

[Peter Morris]

Check my other post, it's a faster approach that doesn't seem to work at a

constant speed.

"seems to work at a constant speed" - took 0.1 seconds to work out all
factors of int.MaxValue