Ошибка при поиске больших простых чисел

Question

Я сделал простую решетку программы erastothenes для вычисления суммы простых чисел до n для эйлера проекта. Он отлично работает на 100, 1000, 10000 и так далее, но когда я делаю 1 или 2 миллиона, это дает мне это:

java.lang.ArrayIndexOutOfBoundsException: -2146737495

Это не происходит при меньших чисел, я использую логические массивы.

boolean[] primes = new boolean[2000001]; 
    ArrayList<Integer> list = new ArrayList<Integer>(); 
    for (int i = 2; i < primes.length; i++){ 
     primes[i] = true; 
    } 
    boolean stop = false; 
    int target = 2; 
    int cycles = 1; 
    while (!stop) { 
     list.add(target); 
     for (int i = target;; i ++) // 
     { 
      if (target*i >= primes.length) {// 
       break; 
      } 
      primes[target*i] = false;// 

     } 
     for (int i = target + 1; ; i ++) { 

      if(i >= primes.length) { 
       stop = true; 
       break; 
      } 
      else if (primes[i]) { 
       target = i; 
       break; 
      } 
     } 
     cycles ++; 
    } 
    int sum = 0; 
     for (int i = 0; i < list.size(); i++) { 
     sum += list.get(i);; 
    } 

Моя цель не совсем реально, чтобы найти ответ, но я много раз отказался от моего кода из-за этих типов ошибок. Я бы хотел найти источник для них.

Answer 1

Это потому, что вы используете Int, который имеет верхний предел 2^31-1: см https://en.wikibooks.org/wiki/Java_Programming/Primitive_Types

Для обработки больших чисел, вы должны использовать BigInteger класс.

Answer 2

У вас проблема с тобой primes массив.

Прежде всего, прочитав ошибку, ваш массив явно недостаточно длинный для вашей логики, так как вы определяете его как boolean[] primes = new boolean[2000001];, и у вас есть ArrayIndexOutOfBoundsException -2146737495.

Так что старайтесь использовать длинный или BigInteger вместо int для переменных i, target и cycles. Тем не менее, вам придется переосмыслить свою логику, поскольку проблема не является переполнением сама по себе, а массивом, который недостаточно длинный.

Answer 3

У вас есть ошибочная проверка, которая не учитывает переполнение целого числа.

for (int i = target;; i ++) // 
{ 
    if (target*i >= primes.length) {// This is the check 
     break; 
    } 
    primes[target*i] = false;// Here is where it overflows 

} 

После того, как вы нажмете i, что делает target * i больше, чем целое число может содержать, целые переполнению. Это означает, что теперь это станет отрицательным. И, конечно, для отрицательного числа target*i >= primes.length будет ложным.

И, конечно, отрицательное число не может быть индексом в массиве. Он должен был остановиться при разрыве, но это произошло не потому, что условие не было выполнено.

Что вы должны сделать, это рассчитать максимальную i, что разрешено, и положить, что в качестве условия цикла:

int maxI = primes.length/target; 
for (int i = target; i < maxI; i ++) // 
{ 
    primes[target*i] = false;// Here is where it overflows 
} 

maxI является максимальное число, которое вы можете умножить на target и до сих пор не достигают primes.length , Теперь вам больше не нужен ваш чек (потому что умножение target на i никогда не даст число больше primes.length. И оно также никогда не будет переполняться, так как умножение всегда дает число, меньшее размера массива, следовательно, меньше . чем Integer.MAX_VALUE

другой метод менее дорогой (меньше умножений) будет:

if (primes.length/target >= target) { 
    for (int i = target * target; i < primes.length; i += target) // 
    { 
     primes[i] = false; 
    } 
} 

проверка в if необходимо, чтобы избежать переполнения в случае, если у вас есть огромный target.