2

我已经开始学习用 Java 编写代码，并决定使用Project Euler站点给我一些小任务，让我尝试完成所学的每一点新代码。所以我遇到了问题3：

13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？

我考虑了这个问题并研究了许多关于素数的不同理论，以及如何通过各种不同的计算找到它们（埃拉托色尼筛就是一个例子），我想出的解决方案是测试 2 --> n 中的数字，看看是否它们是质数，如果是，那么我会将 Tn 变量（在本例中为 600851475143）除以新发现的质数，看看它是否是一个因子。如果是，我会将其分配给变量 Hp（最高质数），并在程序结束时将 Hp 输出到控制台以给出我的结果。

这是我的代码：

public class Largest_Prime_Factor_NEW_SOLUTION {

    static long Tn = 600851475143L;
    static long Hp = 0;
    static boolean isPrime = false;

    public static void main(String[] args) {

        for (long i=2; i<Tn; i++) {
            System.out.println("TESTING NUMBER " + i);
            for (long k=2; k < i; k++) {
                if (i % k == 0) {
                    System.out.println(i + " IS NOT A PRIME");
                    break;
                } else if (k + 1 == i) {
                    isPrime = true;
                }
            }

            if (isPrime) {
            System.out.println(i + " IS A PRIME");
            if (Tn % i == 0) {
                System.out.println(Tn + " IS DIVISIBLE BY " + i);
                Hp = i;
            } else {
                System.out.println(Tn + " IS NOT DIVISIBLE BY " + i);
            }
            }

            isPrime = false;
        }
        System.out.println("THE HIGHEST PRIME NUMBER OF " + Tn + " IS " + Hp);
    }
}

现在我知道这段代码效率很低，刚开始我已经设法从我开始的地方压缩它（到处都是循环！）但我要问的是，我该如何改进呢？它正在吞噬我，因为我研究的所有内容都与其他人会做的事情相矛盾，而且非常令人困惑。我已经尝试过筛法，但我知道布尔数组只能是 int 数组，而不能是长数组？

我知道，当开始编写代码时，我将受限于我可以使用的知识，但出于兴趣，我很想看看最终的解决方案是什么。

4

6 回答 6

6

您可以做的是找到 的最低除数Tn。假设是p，再次找到最低除数Tn/p，以此类推。

现在，每一步p都是素数[解释如下]。所以收集它们，它们是 的主要因数Tn。

为了获得更好的时间复杂度，您可以检查除数高达ceil(sqrt(Tn))仅，而不是Tn-1。

当您开始检查 的主要除数时Tn，您可以从 开始2。一旦你得到一个素数p，就不要从2for重新开始Tn/p。因为,Tn/p也是 的一个除数，Tn并且因为Tn没有小于的除数p，所以也Tn/p没有它。所以重新开始p[p可以有多个权力Tn]。若不p分Tn，移至p+1。

例子 ：

Tn = 45
1. 从 2 开始。2 不整除 45。2
. 下一个测试是针对 3。45 可以被 3 整除。所以 3 是它的一个素数。
3. 现在检查 45/3 = 15 的素数除数，但从 3 开始，而不是从 2 开始。4. 嗯，15 可以被 3 整除。所以从 15/3 = 5 5. 注意 5，ceil(sqrt(5)) 是 3。但是 5 不能被 3 整除。但是因为 4 > ceil(sqrt( 5)) 我们可以毫无疑问地说 5 是素数。

所以 45 的主要除数是 3 和 5。

为什么一个数的最小除数（除了 1）是素数？

假设上述陈述是错误的。然后一个数 N 有一个最小的复合除数，比如 C。

所以 C|N 现在 C 是合数，所以它的除数小于自身但大于一。
假设 C 的除数是 P。
所以 P|C ，但我们有 C|N => P|N，其中 1 < P < C。

这与我们假设 C 是 N 的最小除数相矛盾，因此数字的最小除数始终是素数。

于 2013-07-21T10:40:11.980 回答
1

感谢您的所有帮助，在阅读了评论和答案后，我设法将代码进一步压缩为以下内容：

    public class Largest_Prime_Factor_NEW_SOLUTION_2 {

    static long Tn = 600851475143L;

    public static void main(String[] args) {

        for (long i = 2; i < Math.sqrt(Tn); i++) {

            if(Tn % i == 0) {
                Tn = Tn / i;
                i--;
            }   
        }
        System.out.println(Tn);
    }
}

它完美无缺！再次感谢您的帮助和帮助我理解的时间。我知道这更像是一个数学问题而不是编码问题，但它帮助我理解了一些事情。我现在要去学别的东西了：）

于 2013-07-21T12:33:39.460 回答
0

通过试除法分解合数的简单算法如下所示：

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            fs.append(f)
            n := n / f
        f := f + 1
    if n > 1
        fs.append(n)
    return fs

该算法可以改进，并且有更好的算法来分解大数，但这足以完成您的任务。当你准备好更多时，我谦虚地推荐我博客上的用质数编程的文章 ，其中包括该算法的实现以及其他在 Java 中的实现。

于 2013-07-21T12:25:33.070 回答
0

有很多方法可以改进这样的程序，但改进主要与数学而不是编程有关：

  • 在寻找因子时，检查每个数字，而不仅仅是质数。如果你找到一个因素，检查它是否是素数。通过这种方式，您将避免进行许多素性检查。

  • 一个合数的最大素数最多可以是该数的平方根，因此您可以提前停止迭代。

  • 使用快速素性测试而不是进行试验划分http://en.wikipedia.org/wiki/Primality_test

再说一次，这是一次性的。不要过于复杂。

于 2013-07-21T10:56:22.493 回答
0

既然你是作为一个学习练习来做的，当你已经足够改进你当前的程序时，为什么不尝试用不同的方式解决同样的问题呢？费马分解法首先找到大因子。

于 2013-07-21T11:06:30.110 回答
0

这是这个的java版本：

 static boolean isPrime(int n){
    if (n == 2) return true;
    if (n == 3) return true;
    if (n % 2 == 0) return false;
    if (n % 3 == 0) return false;

    int i = 5;
    int w = 2;
    while (i * i <= n) {
        if(n % i == 0)
        return false;

        i += w;
        w = 6 - w;
    }
    return true;
}

正如@Alexandru 所述：它是经典 O(sqrt(N)) 算法的变体。它使用素数（除了 2 和 3）是 6k-1 和 6k+1 形式的事实，并且只查看这种形式的除数。

于 2015-06-29T09:02:58.413 回答