"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.co m>
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<intFactors Of(int value)
{
List<intresult = new List<int>();
List<intprimeNu mbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prim e);
value = value / prime;
}
}

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

Pete

[Jeroen Mostert]

Peter Morris wrote:

Try something like this

public List<intFactors Of(int value)
{
List<intresult = new List<int>();
List<intprimeNu mbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prim e);
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<intFindFac tors( 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******@xs4al l.nlwrote in message
news:48******** *************@n ews.xs4all.nl.. .

Peter Morris wrote:

>Try something like this

public List<intFactors Of(int value)
{
List<intresult = new List<int>();
List<intprimeNu mbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prim e);
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******@xs4al l.nlwrote in message
news:48******** *************@n ews.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******** ******@TK2MSFTN GP02.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<intFindFac tors( 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******@xs4al l.nlwrote in message
news:48******** *************@n ews.xs4all.nl.. .

>Peter Morris wrote:

>>Try something like this

public List<intFactors Of(int value)
{
List<intresult = new List<int>();
List<intprimeNu mbers = new List<int{ 2, 3, 5, 7, 11, etc };
while (value 1)
{
foreach (int prime in primeNumbers)
if (value % prime == 0)
{
result.Add(prim e);
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 :-)