用于java或scala中的整数分解的库

Question

关于如何实现分解有很多问题,但是对于生产用途,我宁愿使用开源库来获得高效的东西并立即进行测试.我正在寻找的方法如下:

static int[] getPrimeFactors(int n)

对于n = 12,它将返回{2,2,3}

库也可能具有处理long或甚至BigInteger类型的重载

问题不是关于特定的应用程序,而是关于有一个处理这个问题的库.许多人认为根据数字的范围需要不同的实现,在这方面,我希望库在运行时选择最合理的方法.

通过高效我并不意味着"世界上最快"(我不会在JVM上工作......),我只是意味着在一秒而不是一小时内处理int和long range.

Answer 1

我在scala中尝试过这个函数。这是我的结果：

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
}

我尝试让它尽可能实用。
if (i % mod == 0) loop(i / mod, mod, mod :: primes)检查我们是否找到除数。如果我们这样做，我们将它添加到素数并将 i 除以 mod。
如果我们没有找到新的除数，我们就增加除数。
loop(i, 2, Nil).reverse初始化函数并对结果进行递增排序。