Primzahlen generieren

[JavaNoobOfDoom]

Hey Leute ich mal mir mal Code zusammengebastelt um Primzahlen zu generieren (brauchte ich für ein Projekt) aber bei sehr großen mengen (100.000.000+) wird sie sehr langsam. Ich vermute mal dass es eine deutlich bessere Möglichkeit gibt, Primzahlen zu generieren, die ich bisher noch nicht gefunden habe. Habt ihr ne Idee wie ich entweder diese Methode schneller machen kann oder eine komplett andere Möglichkeit zum generieren?

public static int randomPrimeNumber(int pMax)
    {
        if(pMax>=1) {
            boolean prime[]=new boolean[pMax];
            for(int i=0; i<pMax; i++) {
                prime[i]=true;
            }


            for(int i=1; i<pMax; i++) {
                if(prime[i]) {
                    int temp=0;
                    int position=2;


                    while(temp<pMax) {
                        try {
                            prime[(position*(i+1))-1]=false;
                        } catch (ArrayIndexOutOfBoundsException e) {}
                        position++;
                        temp=position*(i+1);
                    }
                }
            }


            while(true) {
                int random=(int)(Math.random()*pMax);
                if(prime[random]) {
                    return random+1;
                }
            }
        } return 0;
    }

 

[Tobse]

Deine "PRimzahlprüfung" ist ziemlich kompliziert, das geht deutlich einfacher (zumal du das prime-Array bei jedem Aufruf neu berechnest).
Um solche Algorithmen schnell zu halten prüft man auch oft nicht, ob eine Zahl tatsächlich eine Primzahl ist sondern ob eine Zahl mit einer Gewissen (ziemlich geringen) Wahrscheinlichkeit keine Primzahl ist. Siehe dazu: Google "probabilistischer Primzahltest"

 

[Enceladus271]

Also deine Lösung zur Erzeugung von Primzahlen ist wie Tobse schon sagte ziemlich kompliziert (außerdem nicht ganz korrekt: Bei randomPrimeNumber(50) habe ich einmal 50 als Rückgabe erhalten).

Ich glaube nicht, dass es Sinn macht alle Primzahlen von 1 bis n zu erzeugen und dann eine zufällig zu wählen. Es würde mehr Sinn machen einfach die erzeugten Zufallszahlen normal zu testen:

    public static boolean isPrime( int n ) {
        if ( n < 2 ) {
            return false;
        }
        final int loopend = (int) Math.sqrt( n );
        for ( int i = 2; i <= loopend; i++ ) {
            if ( n % i == 0 ) {
                return false;
            }
        }
        return true;
    }

    public static int getRandomPrimeNumber( int pMax ) {
        final Random random = new Random();
        while ( true ) {
            final int nextInt = random.nextInt( pMax );
            if ( isPrime( nextInt ) ) {
                return nextInt;
            }
        }
    }

Laut der Primzahlfuktion Pi(x) sind etwa 5% der Zahlen zwischen 0 und Integer.MAX_VALUE Primzahlen. Im Durchschnitt muss die Methode also nur 20 Zahlen testen bis die erste Primzahl gefunden wird.

 

[JavaNoobOfDoom]

Ja bei randomPrimeNumber(n) kann auch n rauskommen ist mir grad aufgefallen ^^ Danke für die hilfreiche Antwort es hat gut funktioniert

 

[stg]

Siehe auch BigInteger (Java Platform SE 7 )
und https://en.wikipedia.org/wiki/AKS_primality_test#Algorithm

 

[Natac]

Warum berechnest du dir nicht 1x alle Primzahlen zwischen 1 und Integer.MAX_VALUE und wählst dann nur noch zufällig eine aus? Das sollte auf Dauer schneller und (imo) einfacher sein, als immer neue Primzahlen zu ermitteln und davon dann eine zufällig auszuwählen.

 

[Enceladus271]

Ist die Frage wie oft man eine zufällige Primzahl braucht und wieviel Arbeitsspeicher man zur Verfügung hat. Es liegen etwa 100.000.000 Primzahlen zwischen 0 und MAX_VALUE. Das heißt die Primzahlen würden 400 MB Arbeitsspeicher belegen. Und es würde auch wahrscheinlich mehrere Sekunden dauern alle diese Zahlen zu berechnen.