Пытаясь учесть длинные слова в 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

У вас серьезные проблемы с целочисленными переполнениями. isInt () никогда не вернет true, если d ≥ 2^31. С другой стороны, isPrime () вернет "истину", если d дважды простое число ≥ 2 ^ 31.

Из любопытства я хотел бы знать, как долго работает этот код. Это должно быть меньше миллисекунды, но я подозреваю, что ваша версия заняла немного больше времени. (Возможно, я неправильно понял ваш вопрос. Может быть, у вас не хватает памяти, но не хватает времени).

Если вы попробуете другие проблемы Project Euler: не пытайтесь решать проблемы буквально. Вам определенно не нужен список всех факторов, чтобы найти наибольшее простое число числа.