Переполнение стека при вычислении 10,001-го простого числа в Java
Я делаю проблему 7 из Euler Проекта. То, что я, как предполагается, делаю, вычисляют 10,001-е простое число. (Простое число является целым числом, больше, чем то, которое является только делимым отдельно и один.)
Вот моя текущая программа:
public class Problem7 {
public static void main(String args[]) {
long numberOfPrimes = 0;
long number = 2;
while (numberOfPrimes < 10001) {
if (isPrime(number)) {
numberOfPrimes++;
}
number++;
}
System.out.println("10001st prime: " + number);
}
public static boolean isPrime(long N) {
if (N <= 1)
return false;
else
return Prime(N, N - 1);
}
public static boolean Prime(long X, long Y) {
if (Y == 1)
return true;
else if (X % Y == 0)
return false;
else
return Prime(X, Y - 1);
}
}
Это работает хорошо с открытием, скажем 100-е простое число, но работающий с очень большими исходными данными (такой как 10 001) результаты в переполнении стека. Да ведь и как я могу зафиксировать это?
8 ответов
Я думаю, проблема в том, что вы рекурсивно вызываете Prime , чтобы определить, является ли число простым или нет. Итак, чтобы определить, является ли число 1000 простым или нет, вы набираете Prime 1000 раз рекурсивно. Каждый рекурсивный вызов требует, чтобы данные хранились в стеке. Стек настолько велик, что в конечном итоге у вас заканчивается место в стеке, чтобы продолжать выполнять рекурсивные вызовы. Попробуйте использовать итеративное решение вместо рекурсивного.
Ваша стратегия проверки простого числа состоит в том, чтобы проверить его делимость с каждым меньшим натуральным числом.
Если вы измените свою стратегию на проверку делимости только с каждым меньшим простым числом, вы сэкономите массу вычислений.
Вам следует сохранить все полученные простые числа в поисковом списке, поэтому вы будете проверять, делится ли число на числа из этого список. Если не простое число - иди добавь его в список.
Еще одна идея - заменить число ++; на число + = 2; и начать проверку с 3 , как только четные числа будут исключение для 2 не простые.
Чтобы решить эту проблему в целом, вам придется переключиться с рекурсивного решения на итеративное. (Каждый рекурсивный алгоритм также может быть выражен итеративно.)
Поскольку функция Prime является рекурсивной, всегда будет существовать системное ограничение на то, сколько раз она может вызывать сама себя.
Однако в вашей системе может быть достаточно памяти для достижения 10001. Java позволяет вам установить максимальный объем памяти (стек, куча и т. Д.), Который использует виртуальная машина. Увеличьте количество памяти стека, и вы, вероятно, сможете это сделать. См. Эту страницу
http://docs.sun.com/source/817-2180-10/pt_chap5.html
для некоторых опций Java VM.
Используйте « Сито Эратосфена »
Источник на Java:
public class Main {
public static void main(String args []){
long numberOfPrimes = 0;
int number = 1;
int maxLimit = 10000000;
boolean[] sieve = new boolean[maxLimit];
for ( int i = 2; i < maxLimit; i++ ) {
if ( sieve[i] == true ) continue;
numberOfPrimes++;
if ( numberOfPrimes == 10001 ) {
number = i;
break;
}
for ( int j = i+i; j < maxLimit; j += i )
sieve[j] = true;
}
System.out.println("10001st prime: "+ number);
}
}
Вы всегда можете использовать Rabin -Миллер тест на простоту. Это очень простой в реализации алгоритм и очень быстрый, хотя понять, как он работает, немного сложнее.
Компиляторы для некоторых языков (например, многих функциональных и полуфункциональных языков, таких как Lisp) преобразуют хвостовую рекурсию, как вы использовали, в итерацию, но (очевидно) компилятор Java делает это не за вас. В результате каждый рекурсивный вызов использует пространство стека, и в конечном итоге вы исчерпываете его, и стек переполняется.
Конечно, для большинства целей вы захотите использовать другой алгоритм - то, что вы используете сейчас, довольно ужасно в таких случаях. По крайней мере, вам нужно проверить нечетные числа только до квадратного корня из числа, которое вы тестируете ...
Я недавно решил эту проблему. Я предлагаю генерировать простые числа с помощью Сита Эратосфена , скажем, все простые числа <1 миллиона. Это несложный для реализации алгоритм, и он довольно быстр для необходимого количества простых чисел.