Переполнение стека при вычислении 10,001-го простого числа в Java
https://stackoverflow.com/questions/2485620
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я решаю задачу 7 проекта Euler.То, что я должен сделать, это вычислить 10,001ST простое число.(Простое число - это целое число, большее единицы, которое делится только на себя и единицу.)
Вот моя текущая программа:
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) приводит к переполнению стека.Почему и как я могу это исправить?
Решение
Я думаю, проблема в том, что вы рекурсивно вызываете Prime определить, является ли число простым или нет.Итак, чтобы определить, является ли число 1000 простым или нет, вы звоните Prime 1000 раз рекурсивно.Каждый рекурсивный вызов требует, чтобы данные хранились в стеке.Стек настолько велик, что в конечном итоге в стеке заканчивается место для выполнения рекурсивных вызовов.Попробуйте использовать итеративное решение вместо рекурсивного.
Другие советы
Использовать "Решето Эратосфена"
Источник 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);
}
}
Вам следует сохранить все простые числа, которые вы получили на данный момент, в список поиска, поэтому вы будете проверять, делится ли число на числа из этого списка.Если нет, то это простое число — добавьте его в список.
Другая идея — заменить number++; с number += 2; и начните проверку с 3 как только четные числа, за исключением 2 не являются простыми.
Недавно я решил эту проблему.Я бы предложил сгенерировать ваши простые числа с помощью Решето Эратосфена, скажем, все простые числа < 1 миллиона.Это несложный алгоритм для реализации, и он довольно быстр для того количества простых чисел, которое вам нужно.
Компиляторы для некоторых языков (например.многие функциональные и полуфункциональные языки, такие как Lisp), преобразуют хвостовую рекурсию, которую вы использовали, в итерацию, но (очевидно) компилятор Java не делает этого за вас.В результате каждый рекурсивный вызов использует пространство стека, и в конечном итоге оно заканчивается, и стек переполняется.
Конечно, для большинства целей вам нужно использовать другой алгоритм — то, что вы используете сейчас, довольно ужасно.По крайней мере, вам нужно проверять только нечетные числа до квадратного корня из числа, которое вы тестируете...
Ваша стратегия проверки простого числа — проверить его делимость на каждое меньшее натуральное число.
Если вы измените свою стратегию на проверку делимости только для каждого меньшего простого числа, вы сэкономите массу вычислений.
import java.util.*;
public class LargestPrime {
public static boolean isPrime(long s) {
for(long i = 2; i < s; i++) {
if((s % i) == 0) return false;
}
return true;
}
public static void main(String[] args) {
LargestPrime p = new LargestPrime();
LinkedList<Long> arr = new LinkedList<Long>();
for(long j = 2; j <= 999999; j++) {
if(isPrime(j)) arr.add(j);
}
// System.out.println("List of Prime Number are: "+ arr);
long t = arr.get(10001);
System.out.println("The Prime Number At 10001st position: " + t);
}
}
Чтобы решить эту проблему в целом, вам придется переключиться с рекурсивного решения на итеративное.(Каждый рекурсивный алгоритм также можно выразить итеративно.)
Поскольку функция Prime является рекурсивной, всегда будет существовать системное ограничение на количество вызовов самой себя.
Однако в вашей системе может быть достаточно памяти для достижения 10001.Java позволяет вам установить максимальный объем памяти (стека, кучи и т. д.), который использует виртуальная машина.Увеличьте количество памяти стека, и вы, вероятно, сможете это сделать.См. эту страницу
http://docs.sun.com/source/817-2180-10/pt_chap5.html
для некоторых опций Java VM.
Вы всегда можете использовать Рабин-Миллер тест на примитивность.Это очень простой в реализации алгоритм и очень быстрый, хотя понять, как он работает, немного сложнее.
package problems;
public class P_7 {
/**
* @param args
*/
public static boolean prime(double num)
{
double x=2;
double limit=(int) ((num/2)-(num/2)%1);
while(x<=limit)
{
if(num%x==0)
return false;
x++;
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int i=1;
int j=3;
while(i<=10000)
{
if(prime(j))
{
System.out.println(i);
i++;
System.out.println(j);
}
j++;
}
}
}
это мой рабочий ответ.
В С...Вы можете сделать более короткую версию, но неважно :D ..
#include <stdio.h>
#include <stdlib.h>
prost_br(int p)
{
int br=0;
for(int i=2;i*i<=p;i++)
if(p%i==0)
br++;
if(br==0)
return 1;
return 0;
}
int main()
{
long i=1;
int br=0;
FILE *a;
a=fopen("10001_prst_numbers.txt","w");
if(a==NULL){printf("\nError!\a\n"); exit(1);}
while(br!=10001)
{
i++;
if(prost_br(i))
{
br++;
fprintf(a,"%d ",i);
}
}
char s[]={"10001th prime number is: "};
fprintf(a,"\n%s %d",s,i);
fprintf(stdout,"\n10001th prime number is: %d\n\a",i);
fclose(a);
system("Pause");
}
Проблема заключается в том, что рекурсивно определенный Prime(X,Y) функция, но также и в используемом алгоритме.Рекурсии существует не так уж много глубина это механизм вызова функций Java может учесть до того, как стек вызовов будет исчерпан, вызывая ошибку "переполнение стека".
Достаточно проверить делимость на все числа, меньшие квадратного корня из проверяемого числа.С точки зрения операционного кода, это означает, что начинать нужно не с Prime(N,N-1), но скорее от Prime( N, floor( sqrt( N+1)) ).Одного этого изменения может быть достаточно, чтобы предотвратить ошибку SO для этой конкретной задачи, поскольку глубина рекурсии изменится с 10000 всего до 100.
Алгоритмические проблемы только начинаются.Тот самый Prime(X,Y) количество кодов вниз, таким образом, сначала проверяя число большими числами.Но меньшие факторы встречаются гораздо чаще;подсчет должен производиться с наименьшим возможным коэффициентом 2 (который встречается для 50% чисел)., вверх к тому sqrt номера кандидата.Функция должна быть переписана как простая while воспользуйтесь и этой возможностью.
Следующее простое и очевидное улучшение - это полное игнорирование четных чисел.известно, что 2 является простым числом;все остальные эвены таковыми не являются.Это означает запуск цикла с numberOfPrimes = 1; number = 3; и подсчитывать по number += 2 для перечисления только нечетных чисел, имеющих isPrime(N) проверяйте их делимость только с помощью странно числа, а также, в while цикл, начинающийся с X = 3, тестирование на N % X и подсчитывать по X += 2.
Или в псевдокод (на самом деле, Haskell), исходный код является
main = print ([n | n<-[2..], isPrime(n)] !! 10000) where
isPrime(n) = _Prime(n-1) where
_Prime(y) = y==1 || (rem n y > 0 && _Prime(y-1))
-- 100:0.50s 200:2.57s 300:6.80s 10000:(projected:8.5h)
-- n^2.4 n^2.4
предлагаемое исправление:
main = print ((2:[n | n<-[3,5..], isOddPrime(n)]) !! 10000) where
isOddPrime(n) = _Prime(3) where
_Prime(y) = (y*y) > n || (rem n y > 0 && _Prime(y+2))
-- 100:0.02s 200:0.03s 300:0.04s 5000:3.02s 10000:8.60s
-- n^1.5
Указанные тайминги относятся к некомпилированному коду в GHCi (на медленном ноутбуке). Эмпирические локальные порядки роста принимаемый как log(t2/t1) / log(n2/n1).Еще быстрее выполняется тестирование простыми числами, а не нечетными.
кстати, исходный код выводит не 10001-е простое число, а число над ним.
программы общественного класса {
public int nthPrime(int nth) {
int ctr = 0;
int num = 0;
int x = 2;
int infinite = 15; // initial value good for 6 prime values
while(x < infinite) {
boolean isPrime = true;
for(int i = 2; i <= x / 2; i++) {
if(x % i == 0) {
isPrime = false;
}
}
if(isPrime) {
System.out.println(x); // optional
ctr++;
if(ctr == nth) {
num = x;
break;
}
}
x++;
if(x == infinite) { // for bigger nth requested prime value
infinite++;
}
}
return num;
}
public static void main(String[] args) {
int ans = new progs().nthPrime(10001);
System.out.println("nth prime number is " + ans);
}
}
