6

关于如何实现分解有很多问题，但是对于生产用途，我宁愿使用开源库来立即获得高效且经过良好测试的东西。我正在寻找的方法如下所示：

static int[] getPrimeFactors(int n)

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

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

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

高效并不是指“世界上最快的”（我不会为此在 JVM 上工作……），我只是指在一秒钟而不是一小时内处理 int 和 long range。

4

4 回答 4

4

这取决于你想做什么。如果您的需求不大（例如，您想解决Project Euler问题），Pollard 的 rho 算法的简单实现将立即找到高达 10 或 12 位的因子；如果这是您想要的，请告诉我，我可以发布一些代码。如果您想要一个用 Java 编写的更强大的因式分解程序，您可以查看 Dario Alpern 的小程序背后的源代码；我不知道测试套件，它真的不是用开放的 api 设计的，但它确实有很多用户并且经过了很好的测试。大多数重型开源分解程序都是用 C 或 C++ 编写的，并使用 GMP 大整数库，但您可以通过您语言的外部函数接口访问它们；msieve、pari或yafu。如果这些不满足您，寻求更多帮助的好地方是Mersenne 论坛。

于 2012-07-23T14:23:57.560 回答
1

如果你想解决你的问题，而不是得到你想要的，你想要一张桌子。您可以使用愚蠢的慢速方法预先计算它，存储它，然后以微秒为单位查找任何数字的因子。特别是，您想要一个表格，其中最小因子列在与数字对应的索引中 - 如果您使用试除法删除一些最小的素数，内存效率会更高 - 然后沿着表格向下走，直到你打了一个 1（意味着没有除数；你剩下的是素数）。每个表条目只需要两个字节，这意味着您可以将所有内容存储在比智能手机更重的任何现代机器上。

如果您有兴趣，我可以演示如何创建它，并展示如何以比您希望通过一个活跃的社区和复杂算法的单元测试实现的可靠性更高的可靠性来检查它是否正确（除非您运行算法来生成此表并验证一切正常）。

于 2012-07-23T17:25:40.687 回答
0

我需要它们来测试多项式是否是原始的。

这比试图找出所有数字的因数要快。

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;
}
于 2012-07-23T14:06:15.977 回答
-2

我在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初始化函数并对结果进行递增排序。

于 2012-07-23T12:14:22.970 回答