-2 
import java.math.BigInteger;
public class ProjectEuler {
    public static void main(String[] args) {
        BigInteger bi = new BigInteger("600851475143");
        int div = 7;
        while (bi.compareTo(new BigInteger("1")) != 0) {
            while (bi.mod(new BigInteger(div + "")).compareTo(new BigInteger("0")) == 0) {
                bi = bi.divide(new BigInteger(div + ""));
            }
            div += 2;
        }
        System.out.println("" + div);
    }
}

我只是在研究“什么是数字 600851475143 的最大素数”这个基本但著名的问题之一。我发现这个解决方案不同，我有几个关于它是如何工作的问题。

  1. 第一个条件检查数字是否等于 1。从那里我无法理解其余的代码。
  2. new BigInteger(div +""). 为什么我们在这里连接+“”？
4

2 回答 2

2

div = 7 是怎么决定的？

作者决定“硬编码”他对数字本身的了解，以决定前三个素数不在除数之内

第一个条件检查数字是否等于 1。从那里我无法理解其余的代码。

其余代码在“常规”整数中如下所示：

while (bi % div == 0) {
    bi /= div;
}
div += 2;

new BigInteger(div +"")为什么我们+ ""在这里连接

这是使对象 a 的一种简短方法String。 BigInteger有一个参数String，所以这种方法的替代方法是调用Integer.toString(div).

请注意，这不是最有效的解决方案：可以通过观察到当您达到原始数字的平方根时停止尝试除法来加快这一速度，因为您可以确定下一个除数将是数字本身。

于 2013-06-16T22:41:24.723 回答
1

div = 7 是怎么决定的？

可能作者注意到这个数字不能被 2 或 3 或 5 整除。要知道作者是如何做到这一点的，他/她应该知道这个规则：Divisibility Rules and Tests

第一个条件检查数字是否等于 1。从那里我无法理解其余的代码。

作者确保数字不是BigInteger("1") ，因为它将数字除以并将结果存储在bi循环迭代中。请注意：

bi = bi.divide(new BigInteger(div + ""));

new BigInteger(div +""). 为什么我们在这里连接+“”？

它使用BigInteger(String)构造函数。作者 n̶a̶i̶v̶e̶l̶y̶String通过添加int一个空的 来创建一个新的String。

于 2013-06-16T22:41:05.567 回答