Я столкнулся со странной проблемой для задачи 3 проекта Euler. Программа работает для других небольших чисел, таких как 13195, но выдает эту ошибку, когда я пытаюсь вычислить большое число, например 600851475143:

 Exception in thread "main" java.lang.ArithmeticException: / by zero
    at euler3.Euler3.main(Euler3.java:16)
  

Вот мой код:

     //Number whose prime factors will be determined
    long num = 600851475143L;

    //Declaration of variables
    ArrayList factorsList = new ArrayList();
    ArrayList primeFactorsList = new ArrayList();

    //Generates a list of factors
    for (int i = 2; i < num; i  )
    {
        if (num % i == 0)
        {
            factorsList.add(i);
        }           
    }

    //If the integer(s) in the factorsList are divisable by any number between 1 
    //and the integer itself (non-inclusive), it gets replaced by a zero 
    for (int i = 0; i < factorsList.size(); i  )
    {
        for (int j = 2; j < (Integer) factorsList.get(i); j  )
        {
            if ((Integer) factorsList.get(i) % j == 0)
            {
                factorsList.set(i, 0);
            }
        }
    }

    //Transfers all non-zero numbers into a new list called primeFactorsList
    for (int i = 0; i < factorsList.size(); i  )
    {
        if ((Integer) factorsList.get(i) != 0)
        {
            primeFactorsList.add(factorsList.get(i));
        }
    }
  

Почему только большие числа вызывают эту ошибку?

Ваш код просто использует Integer 32-разрядный тип с максимальным значением 2147483647. Неудивительно, что он терпит неудачу при использовании для чисел, намного превышающих это. Обратите внимание, что ваш начальный цикл использует int в качестве переменной цикла, поэтому фактически цикл был бы бесконечным, если бы он не создавал исключение. Значение i изменится с 2147483647 на -2147483648 и продолжится.

Используйте BigInteger для обработки произвольно больших значений или Long , если вас устраивает ограниченный диапазон, но больший. (Максимальное значение long / Long равно 9223372036854775807L.)

Однако я сомневаюсь, что это действительно ожидаемый подход… для таких больших чисел потребуется много времени.

Не уверен, что это так, поскольку я не знаю, какая строка какая, но я замечаю, что ваш первый цикл использует int.

 //Generates a list of factors
for (int i = 2; i < num; i  )
{
    if (num % i == 0)
    {
        factorsList.add(i);
    }           
}
  

Поскольку num является длинным, возможно, что num > Integer.MAX_INT и ваш цикл завершается отрицательным значением, MAX_INT затем выполняется цикл до 0, что дает вам num % 0 операцию.

Почему ваше решение не работает?

Числа колодцев являются дискретными в аппаратном обеспечении. Дискретный означает, что у тебя есть минимальное и максимальное значения. Java использует дополнение двух для хранения отрицательных значений, поэтому 2147483647 1 == -2147483648 . Это потому, что для типа int максимальное значение равно 2147483647 . И это называется переполнением.

Кажется, что у вас есть overflow bug . Повторяющееся значение i сначала становится отрицательным и в конечном итоге 0, таким образом, вы получаете java.lang.ArithmeticException: / by zero . Если ваш компьютер может выполнять цикл из 10 миллионов операторов в секунду, для воспроизведения этого потребуется 1 час 10 минут, поэтому я оставляю это как предположение, а не доказательство.

Это также причина, по которой тривиально простые утверждения типа a b могут приводить к ошибкам.

Как это исправить?

 package margusmartseppcode.From_1_to_9;

public class Problem_3 {
    static long lpf(long nr) {
        long max = 0;

        for (long i = 2; i <= nr / i; i  )
            while (nr % i == 0) {
                max = i;
                nr = nr / i;
            }

        return nr > 1 ? nr : max;
    }

    public static void main(String[] args) {
        System.out.println(lpf(600851475143L));
    }
}
  

Вы можете подумать: «Так как же это работает?»

Ну, мой сложный процесс прошел так:

1. (Подход к динамическому программированию) Если бы у меня был список простых чисел x {2,3,5,7,11,13,17, ...} с точностью до значения x_i > nr / 2, то найти наибольший простой множитель тривиально:
   • Я начинаю с самого большого простого числа и начинаю тестировать, равно ли devision reminder с моим номером нулю, если это так, то это ответ.
   • Если после перебора всех элементов я не нашел свой ответ, мое число должно быть простым само по себе.
2. (Грубая сила, с фильтрами) Я предположил, что
   • самый большой простой множитель в моих числах мал (менее 10 миллионов).
   • если мои числа кратны некоторому числу, то я могу уменьшить размер цикла на это кратное.

Здесь я использовал второй подход.

Однако обратите внимание, что если бы мое число было бы немного отклонено и одним из {600851475013, 600851475053, 600851475067, 600851475149, 600851475151} , то мои предположения о подходе потерпели бы неудачу, и программе потребовалось бы смехотворно много времени для запуска. Если бы компьютер мог выполнять 10 миллионов операторов в секунду, потребовалось бы 6,954 дней, чтобы найти правильный ответ.

В вашем подходе с использованием грубой силы простое генерирование списка факторов заняло бы больше времени — при условии, что у вас раньше не заканчивалась память.

Есть ли лучший способ?

Конечно, в Mathematica вы могли бы записать это как:

 P3[x_] := FactorInteger[x][[-1, 1]]
P3[600851475143]
  

или просто FactorInteger[600851475143] и найдите наибольшее значение.

Это работает, потому что в Mathematica у вас есть целые числа произвольного размера. Java также имеет вызываемый класс целых чисел произвольного размера BigInteger .

Помимо BigInteger проблемы, упомянутой Джоном Скитом, обратите внимание на следующее:

1. вам нужно только протестировать коэффициенты до sqrt(num)
2. каждый раз, когда вы находите коэффициент, делите num на этот коэффициент, а затем снова проверяйте этот коэффициент
3. действительно нет необходимости использовать коллекцию для предварительного хранения простых чисел

Мое решение (которое изначально было написано на Perl) выглядело бы примерно так на Java:

 long n = 600851475143L;          // the original input
long s = (long)Math.sqrt(n);     // no need to test numbers larger than this
long f = 2;                      // the smallest factor to test
do {
    if (n % f == 0) {            // check we have a factor
         n /= f;                 // this is our new number to test
         s = (long)Math.sqrt(n); // and our range is smaller again
    } else {                     // find next possible divisor
         f = (f == 2) ? 3 : f   2;
    }
} while (f < s);                 // required result is in "n"