# Primzahlen generieren



## JavaNoobOfDoom (18. Jun 2015)

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 (18. Jun 2015)

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 (18. Jun 2015)

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 (18. Jun 2015)

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


----------



## stg (18. Jun 2015)

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


----------



## Natac (19. Jun 2015)

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 (20. Jun 2015)

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.


----------

