Java 中的欧拉计划 #3；程序不输出结果

Question

我正在尝试解决 Project Euler 中的问题 3：

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

这是我的代码：

import java.util.ArrayList;

public class Test {
    public static void main(String[] args){
        long max = 600851475143L;
        ArrayList<Long> primes = new ArrayList<>();
        primes.add((long) 2);
        boolean prime = true;
        for (long i = 3; i <= max; i += 2){
            for (long j = 3; j < Math.sqrt(i); j++){
                if (i % j == 0){
                    prime = false;
                    break;
                }
            }
            if (prime) primes.add(i);
            else prime = true;
        }
        for (int i = primes.size() - 1; i >= 0; i--){
            if (max % primes.get(i) == 0){
                System.out.println(primes.get(i));
                return;
            }
        }
    }
}

代码没有输出任何内容，只是给我一个空白屏幕。请不要为我解决问题，只要告诉我阻止它输出任何东西的错误是什么。

Answer 1

你在计算所有质数时都在浪费时间，而你却没有。

找到第一个素数后，尝试将 max 减去该素数，直到它不再可整除。
然后继续寻找下一个素数
并通过分解出那个素数来减少最大值。
每次检查max是否等于当前素数。如果是这样，你就完成了。

假设您正确找到了素数（我相信您是正确的），请考虑以下事项：

primes = 2,3,5,7,11,13
max = 99

is 99 divisible by 2 - no, try next prime.
is 99 divisible y  3 -  yes
max = 33
is 33 divisble by 3  - yes 
max = 11
is 11 divisible by 3 - no
by 5 - no
by 7 - no
by 11 - hey, max is a prime! And it must be the largest because
it can't be reduced anymore.

如果你愿意，在找到 max 的每个质因数时，将其保存在列表中。

然后将列表中的所有值相乘，看乘积是否==最大值。

这是您的代码

import java.util.ArrayList;

public class Test {
    public static void main(String[] args){
        long max = 600851475143L;
          // right here, reduce max by current prime (which starts at 2)

        for (long i = 3; i <= max; i += 2){
            boolean prime = true;
            for (long j = 3; j < Math.sqrt(i); j++){
                if (i % j == 0){
                    prime = false;
                    break;
                }
            }
            if (prime)  {
            // right here, reduce max by current prime

            }
        }
    }
}

Answer 2

您确定您的程序正在完成吗？我在下面添加了以下代码，看起来第一个 for 循环需要很长时间才能完成，这可能就是您看不到任何输出的原因。要查看您的进度，请尝试添加如下打印语句：

import java.util.ArrayList;

public class Test {

    public static void main(String[] args){
        long max = 600851475143L;
        ArrayList<Long> primes = new ArrayList<Long>();
        primes.add((long) 2);
        boolean prime = true;
        for (long i = 3; i <= max; i += 2){
            if(i % 1000005 == 0)
                System.out.println("i = " + i);
            for (long j = 3; j < Math.sqrt(i); j++){
                if (i % j == 0){
                    prime = false;
                    break;
                }
            }
            if (prime) primes.add(i);
            else prime = true;
        }
        for (int i = primes.size() - 1; i >= 0; i--){
            if (max % primes.get(i) == 0){
                System.out.println(primes.get(i));
                return;
            }
        }
    }
}

Java 中的欧拉计划 #3；程序不输出结果

Project Euler #3 in Java; program not outputting result

java

primes