java - 项目欧拉数 3 : Largest prime factor

Question

这是我的代码:

public class LargestPrimeFactor {

/**
 * @param args the command line arguments
 */
public static boolean isPrime(long x){
    for (int y=2; y<x; y++){
        if (x%y==0){
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    System.out.println("Find out the largest prime factor of 600851475143");
    long num=600851475143L;
    int largest=0;
    int y=0;
    for (int x=2; x<num; x++){
        if (num%x==0&&isPrime(x)==true){
            System.out.println(x);
        }
    }
    System.out.println(largest);
}

这是输出:

Find out the largest prime factor of 600851475143
71
839
1471
6857
-716151937
-408464633
-87625999
-10086647
-5753023
-1234169
-486847
-104441
-59569
-6857
-1471
-839
-71
-1
Exception in thread "main" java.lang.ArithmeticException: / by zero
    at largestprimefactor.LargestPrimeFactor.main(LargestPrimeFactor.java:32)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 minutes 10 seconds)

如何打印出最大的数字？当“x”应该不断增加而不是减少时，为什么输出显示负数？

更新

这是我编辑的代码:

public static boolean isPrime(long x){
    for (int y=2; y<x; y++){
        if (x%y==0){
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    System.out.println("Find out the largest prime factor of 600851475143");
    long num=600851475143L;
    long largest=0;
    int y=0;
    for (long x=2; x<num/2; x++){
        if (num%x==0&&isPrime(x)==true){
            System.out.println(x);
            if (largest<x){
                largest=x;
            }
        }
    }
    System.out.println(largest);
}

这是新的输出

Find out the largest prime factor of 600851475143
71
839
1471
6857
0
BUILD SUCCESSFUL (total time: 318 minutes 31 seconds)

如何将最终答案打印为“6857”而不是“0”？另外，如果您注意到的话，该程序的运行时间略多于 5 小时。如何加快此过程？

Answer 1

您正在为 for 循环使用 int，该循环已溢出。使用 long 变量进行迭代。

for (int x=2; x<num; x++){
     ^^^

负值的原因是它正在环绕。如果您只想找到最大的，您可以使用一个新的 long 变量来存储迄今为止的 max-seen 。另一种方法是简单地反向迭代范围。

此外，您可以缩短循环以仅检查给定数字的平方根。如果找到一个因子，您可以执行(num/ans)来找到较大的因子。