Integer factors


#1

Hi,

I’ve been looking for a nuget package that will let me find the integer factors (of an integer).
I tried using:

MathNet.Symbolics.Algebraic.FactorsInteger(MathNet.Symbolics.Expression.FromInt32(10))

Unfortunately this returns a tuple containing 10 and an empty array, presumably meaning I’m calling it wrong.

I can’t quite figure out from the documentation how I’m doing this wrong - I’ve just kinda-guessed at how to use it. Could anyone give me a pointer, please?


(Christoph Rüegg) #2

Ah - I guess it would be time to start documenting Symbolics, at least the API itself.

Algebraic.FactorInteger separates integer factors of an expression, e.g. 2/3*b*cos(x) would be separated into 2 and [1/3; b; cos(x)]. This is used e.g. to simplify rational expressions. However, it does not factor the integer itself into prime factors, which I assume is what you’re looking for.

I was just surprised that we indeed do not have any prime factor decomposition over at Math.NET Numerics - we should look into this.


#3

Actually just all integers that divide it evenly (sorry, my maths education was a long time ago!)
So for 10, I’d want 1, 2, 5 and 10.


#4

You can take the implementation, for example, here:


#5

Thanks FoggyFinder, but writing the brute force implementation was simple enough. I was looking for a library which called upon a more efficient algorithm. I’m under the (perhaps false) impression that Pollard’s Rho, amongst others, can reduce the complexity from O(n^2) down to something less painful, but I might be misreading.


#6

Sorry for such a late reply. Pollard’'s Rho allows to find only one number (if I understand the algorithm). If the numbers are many and they are not too large, it is easier to make a list of primes and check on them.