Java で 10,001 番目の素数を計算するとスタック オーバーフローが発生する
https://stackoverflow.com/questions/2485620
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
プロジェクトオイラーの問題7をやっています。私がやるべきことは 10,001 を計算することですセント 素数。(素数とは、1 より大きく、それ自体と 1 でのみ割り切れる整数です。)
私の現在のプログラムは次のとおりです。
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を呼んでいます。各再帰呼び出しはスタック上に保存されるデータを必要とします。スタックはそう最終的にあなたが再帰的コールを保つためにスタック上に部屋を出て実行し、唯一の非常に大きいです。代わりに、再帰的なソリューションの反復解法を使用してみてください。
他のヒント
使用 "ふるいエラトステネスするの"
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からチェックを開始することです。
私は最近、この問題を解決しました。私はすべての素数<100万を言う、エラトステネスするのA ふるいであなたの素数を生成することをお勧めしたいです。これは、実装するのは難しいのアルゴリズムではありません、それはあなたが必要とする素数の数をかなり高速です。
あなたが反復に使用してきたようないくつかの言語（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);
}
}
は、反復1の再帰溶液からスイッチする必要があるとしています。 （すべての再帰的なアルゴリズムは、あまりにも、反復的に表現することができる。）
機能総理は再帰的であるので、常にそれが自分自身を呼び出すことができますどのように多くの時間がシステムの制限が存在します。
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++;
}
}
}
これは私の作業の答えです。
Cでは...短いバージョンでも構いませんが、: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 の関数呼び出しメカニズムは、呼び出しスタックが使い果たされて「スタック オーバーフロー」エラーが発生する前に対応できます。
テスト対象の数値の平方根以下のすべての数値に対して割り切れるかどうかをテストするだけで十分です。OP コードに関して言えば、それは次のことから始めないことを意味します。 Prime(N,N-1), 、むしろから Prime( N, floor( sqrt( N+1)) ). 。再帰の深さが 10000 からちょうど 100 に変更されるため、この変更だけでもこの特定のタスクの SO エラーを防ぐのに十分である可能性があります。
アルゴリズムの問題はそこからしか始まりません。の 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 番目の素数ではなく、その上の数値を出力します。
パブリッククラスprogsの{
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);
}
}
