Stack-Überlauf, wenn der 10,001st Primzahl in Java Berechnung

Question

Ich tue Problem 7 von Project Euler. Was soll ich tun ist, um die 10.001 ^st Primzahl zu berechnen. (A Primzahl ist eine ganze Zahl größer als eins ist, die nur durch sich selbst teilbar ist und eins.)

Hier ist mein aktuelles Programm:

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);
    }
}

Es funktioniert in Ordnung mit Befunde, sagt die 100 ^th Primzahl, aber mit sehr großen Eingängen (wie 10001) Ergebnisse in Stapelüberlauf ausgeführt wird. Warum, und wie kann ich dieses Problem beheben?

Answer 1

Ich denke, das Problem ist, dass Sie Prime rekursiv aufrufen, um zu bestimmen, ob eine Zahl eine Primzahl ist oder nicht. Also, um zu bestimmen, ob die Zahl 1000 Primzahl ist oder nicht, sind Sie Prime 1000 mal rekursiv aufrufen. Jeder rekursive Aufruf erfordert Daten auf dem Stapel gehalten werden. Der Stapel ist nur so groß, Sie so schließlich Platz erschöpft auf dem Stapel rekursive Aufrufe zu halten machen. Versuchen Sie es mit einer iterativen Lösung anstelle einer rekursiven Lösung.

Answer 2

Mit " Sieb des Eratosthenes "

Java Quelle:

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);
    }
}

Answer 3

Sie sollten alle Primzahlen sparen Sie so weit in einen Blick auf die Liste bekam daher werden Sie überprüft werden, wenn die Zahl durch die Zahlen aus dieser Liste unterteilt. Wenn nicht ist es eine Primzahl - gehen sie in die Liste aufnehmen
. Eine weitere Idee ist number++; mit number += 2; zu ersetzen und startet von 3 sobald geraden Zahlen mit Ausnahme für 2 Überprüfung nicht prim.

Answer 4

Ich löste vor kurzem dieses Problem. Ich würde vorschlagen, Ihre Primzahlen mit einem Sieb des Eratosthenes zu erzeugen, sagen alle Primzahlen <1 Million. Es ist kein harter Algorithmus zu implementieren, und es ist ziemlich schnell für die Anzahl der Primzahlen Sie benötigen.

Answer 5

Compiler für einige Sprachen (zum Beispiel viele funktionelle und halb funktionalen Sprachen wie Lisp) konvertiert Endrekursion wie Sie in Iteration verwendet haben, aber (anscheinend) der Java-Compiler tut das nicht für Sie. Als Ergebnis wird mit jeder rekursive Aufruf Stapelspeicher, und Sie schließlich laufen und der Stapel überläuft.

Natürlich, für die meisten Zwecke, möchten Sie einen anderen Algorithmus verwenden - was Sie jetzt verwenden ziemlich schrecklich ist, wie diese Dinge gehen. Zumindest müssen Sie nur ungerade Zahlen bis zur Quadratwurzel der Anzahl Sie testen ...

prüfen

Answer 6

Ihre Strategie ein erstklassigen zu testen, ist die Teilbarkeit mit jeder kleineren natürlichen Zahl zu überprüfen.

Wenn Sie Ihre Strategie Test für Teilbarkeit mit nur jeder kleineren prime verschieben, würden Sie eine ganze Menge Berechnung speichern.

Answer 7

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);
    }
}

Answer 8

Um dies in der Regel zu lösen, Sie gehen von einer rekursiven Lösung zu einem iterativ man Schalter haben. (Jeder rekursive Algorithmus kann iterativ ausgedrückt werden, auch.)

Da Funktion Prime rekursiv ist, wird es immer eine Systemgrenze auf sein, wie oft sie sich nennen kann.

Sie können jedoch auf Ihrem System genügend Speicher erreichen 10001. Java Sie die maximale Speichermenge einstellen kann (Stack, Heap, etc.), dass die VM-Anwendungen. Erhöhen Sie die Stapelspeicher-Nummer, und Sie werden wahrscheinlich in der Lage zu machen. Siehe diese Seite

http://docs.sun.com/source/817 -2.180-10 / pt_chap5.html

für einen Teil der Java-VM-Optionen.

Answer 9

Sie könnten immer verwenden Sie die Rabin-Miller Primzahltest. Es ist ein sehr einfacher Algorithmus zu implementieren und sehr schnell, obwohl zu verstehen, wie es funktioniert etwas schwieriger ist.

Answer 10

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++;
        }
    }
}

Das ist meine Arbeits Antwort.

Answer 11

In C ... Sie können kürzere Version tun, aber was auch immer: 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");
}

Answer 12

Das Problem liegt in der rekursiv definiert Prime(X,Y) Funktion, sondern auch in dem Algorithmus verwendet. Es gibt nur so viel Rekursion Tiefe , dass der Funktionsaufruf Mechanismus von Java aufnehmen kann, bevor der Anruf Stapel erschöpft ist, wodurch der „Stack-Überlauf“ Fehler.

Es ist genug, um Test für Teilbarkeit gegen alle Zahlen unter der Quadratwurzel der Anzahl getestet. In Bezug auf den OP-Code ab, dass Mittel nicht aus Prime(N,N-1), sondern von Prime( N, floor( sqrt( N+1)) ). Diese Änderung allein könnte ausreichen, um die SO Fehler für diese spezifische Aufgabe zu verhindern, da die Rekursionstiefe von 10000 auf nur 100

ändern

algorithmische Probleme nur dort beginnen. Die Prime(X,Y) Code zählt unten , also die Prüfung der Anzahl von größeren Zahlen zuerst. Aber auch kleinere Faktoren sind weit häufiger gefunden; das Zählen sollte aus dem kleinstmöglichen Faktor erfolgen, 2, (die für 50% der Zahlen angetroffen wird) bis auf die sqrt der Kandidatennummer. Die Funktion sollte auch bei dieser Gelegenheit neu geschrieben als einfache while Schleife sein.

Als nächstes einfache und offensichtliche Verbesserung ist die geraden Zahlen ganz zu ignorieren. 2 ist bekannt, dass prime; alle anderen Evens nicht. Das heißt, die Schleife von numberOfPrimes = 1; number = 3; und Aufwärtszählen von number += 2 beginnend nur ungerade Zahlen aufzuzählen, aber auch isPrime(N) testen ihre Teilbarkeit nur durch die ungerade Zahlen, die in einem while Schleife mit X = 3 beginnend, Prüfung auf N % X und Zählen von X += 2.

oder in Pseudo-Code (eigentlich Haskell), der ursprüngliche Code ist

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

Die vorgeschlagene fix:

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

Timings gezeigt werden, sind nicht-kompilierten Code in GHCi (auf einem langsamen Laptop). Empirische lokale Aufträge des Wachstums als log(t2/t1) / log(n2/n1) genommen. Noch schneller durch Primzahlen Testen und nicht durch ungerade Zahlen.

btw, die ursprüngliche Code druckt nicht die 10001. prime, aber die Zahl darüber.

Answer 13

public class 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);
}

}