"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]]

Re: "factor s of" method

<"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 - <skeet@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]

Re: &quot;factor s of&quot; method

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]

Re: &quot;factor s of&quot; method

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]

Re: &quot;factor s of&quot; method

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" <jmostert@xs4al l.nlwrote in message
news:48ab3b96$0 $187$e4fe514c@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]

Re: &quot;factor s of&quot; method

Actually 2 upwards to n / 2 would be sufficient.

"Jeroen Mostert" <jmostert@xs4al l.nlwrote in message
news:48ab3b96$0 $187$e4fe514c@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]

Re: &quot;factor s of&quot; method

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]

Re: &quot;factor s of&quot; method

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]

Re: &quot;factor s of&quot; method

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:ORapMSkAJH A.3756@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" <jmostert@xs4al l.nlwrote in message
news:48ab3b96$0 $187$e4fe514c@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]

Re: &quot;factor s of&quot; method

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]

Re: &quot;factor s of&quot; method

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<i nt, intkvp in result)
Console.WriteLi ne("{0} x {1}", kvp.Key, kvp.Value);
Console.ReadLin e();


Pete

[K Viltersten]

Re: &quot;factor s of&quot; method

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]

Re: &quot;factor s of&quot; method

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.Collecti ons.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplicat ion2
{
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 = FindHighestFact or(lowValue, highValue, sourceValue);

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

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

foreach (KeyValuePair<i nt, intkvp in result)
Console.WriteLi ne("{0} x {1}", kvp.Key, kvp.Value);
Console.ReadLin e();

}

private static int FindHighestFact or(int lowValue, int highValue, int
sourceValue)
{
int currentProduct = lowValue * highValue;
int difference = sourceValue - currentProduct;
if (difference == 0)
return highValue;
return highValue + (int)Math.Ceili ng((double)diff erence / lowValue);

}
}
}

[Peter Morris]

Re: &quot;factor s of&quot; method

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

[Peter Morris]

Re: &quot;factor s of&quot; method

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