试图在 java 中计算多头，但内存不足？

Question

public static void main(String[] args){
    System.out.println("The largest prime factor of 600851475143 is "+largest(primeFactors(600851475143.0)));
}
public static ArrayList<Integer> factor(double n){
    ArrayList<Integer> factors = new ArrayList<Integer>();
    for(long i = 1; i<=n; i++){
        if(isInt(n/i)){
            factors.add((int)i);
        }
    }
    return factors;
}
public static ArrayList<Integer> primeFactors(double n){
    ArrayList<Integer> factors = factor(n);
    ArrayList<Integer> primes = new ArrayList<Integer>();
    for(int f : factors){
        if(isPrime(f)){
            primes.add(f);
        }
    }
    return primes;
}
public static boolean isInt(double d){
    return (d==(int)d);
}
public static boolean isPrime(double d){
    return (factor(d).size()<=2);
}
public static long largest(ArrayList<Integer> integers){
    int max = 1;
    for(int i = 0; i<integers.size(); i++){
        if(integers.get(i)>max){
            max=integers.get(i);
        }
    }
    return max;
}

运行这段代码导致我的 java 抱怨内存不足？我没想到这是一个很难解决的问题，因为我的代码很有意义并且适用于较小的数字，但是这个问题似乎有问题。我的代码中是否存在导致它崩溃的问题，或者仅仅是因为我的代码（或通常的 java）内存效率不高？它可以通过从这个较大的数字中减去数字来完成的最大数字是它正确回答的“60085147.0”。我怎样才能让它解析更大的数字？

Answer 1

您遇到了严重的整数溢出问题。如果 d ≥ 2^31，isInt () 永远不会 return "true"。另一方面，如果 d 是素数的两倍 ≥ 2^31，isPrime () 将 return "true"。

出于好奇，我很想知道这段代码有多长运行。它应该少于一毫秒，但我怀疑你的版本花费了更长的时间。（也许我问错了你的问题。也许你不是运行内存不足，而是时间不足）。

如果您尝试其他 Project Euler 问题：不要尝试从字面上解决问题。您绝对不需要所有因素的列表来找到数字的最大质因数。

试图在 java 中计算多头，但内存不足？

Trying to factor longs in java, out of memory?

memory

crash

factoring