Library for integer factorization in java or scala

Question

There are many questions about how to implement factorization, however for production use I would prefer to use an open source library to get something effective and well tested right away. The method I'm looking for is as follows:

static int[] getPrimeFactors(int n) 

it will return {2,2,3} for n = 12

A library may also have an overload to handle long or even BigInteger types

The question is not in the specific application, but in the fact that it has a library that copes well with this problem. Many people claim that depending on the range of numbers different implementations are required, in this respect I expect the library to choose the most reasonable method at runtime.

Effective I do not mean "the world is faster" (I would not work on the JVM for this ...), I mean that I deal with int and long range for a second, not an hour.

Answer 1

It depends on what you want to do. If your needs are modest (let's say you want to solve Project Euler problems), a simple implementation of the Pollard algorithm rho will find factors up to ten or twelve digits instantly; if this is what you want let me know and i can post the code. If you want to create a more powerful factoring program written in Java, you can see the source code behind the Dario Alpern applet ; I do not know about the test suite, and it really is not developed with an open api, but it has many users and it is well tested. Most powerful open source factoring programs are written in C or C ++ and use the GMP large number library, but you can access them through the external interface of your foreign interface; look for names like gmp-ecm , msieve , pari or yafu . If this does not suit you, the Mersenne Forum is a good place to get more help.

Answer 2

If you want to solve your problem, and not get what you ask for, you need a table. You can precompile it using stupid slow methods, save it, and then look for factors for any number in microseconds. In particular, you need a table in which the smallest coefficient is indicated in the index corresponding to the number - much more memory efficient if you use the trial unit to delete the few smallest primes, and then go through the table until you press 1 (which means no more divisors, but what you have left is simple). It takes only two bytes to write to the table, which means that you can store everything on any modern machine, more powerful than a smartphone.

I can demonstrate how to create this, if you are interested, and show how to verify that it is correct, with more reliability than you could hope to achieve with the help of an active community and unit tests of a complex algorithm (if you did not run the algorithm to create this table and confirmed that everything is in order).

Answer 3

I need them to check if the polynomial is primitive or not.

This is faster than trying to find factors of all numbers.

 public static boolean gcdIsOne(int[] nums) { int smallest = Integer.MAX_VALUE; for (int num : nums) { if (num > 0 && smallest < num) smallest = num; } OUTER: for (int i = 2; i * i <= smallest; i = (i == 2 ? 3 : i + 2)) { for (int num : nums) { if (num % i != 0) continue OUTER; } return false; } return true; } 

Answer 4

I tried this function in scala. Here is my result:

 def getPrimeFactores(i: Int) = { def loop(i: Int, mod: Int, primes: List[Int]): List[Int] = { if (i < 2) primes // might be i == 1 as well and means we are done else { if (i % mod == 0) loop(i / mod, mod, mod :: primes) else loop(i, mod + 1, primes) } } loop(i, 2, Nil).reverse } 

I tried to make it as functional as possible.
if (i % mod == 0) loop(i / mod, mod, mod :: primes) checks if we have found a divisor. If we did this, add it to primes and divide it modulo.
If we did not find a new divisor, we simply increase the divisor.
loop(i, 2, Nil).reverse initializes the function and arranges the result more often.