Primzahlen Algorithmus

[wapplegraph]

Hallo

Ich bin gerade mit Java an einem kleinen Progrämmchen für die Ausgabe von Primzahlen.
Das Problem ist jedoch ener mathematisch.

Der Algorithmus sollte nur funktionieren, also bitte nicht grosse Hinweise auf Leistung.
Mein Algorithmus funktioniert nur bis 7! :-[
Könntet ihr mir einen Hinweis auf meinen Denkfehler geben?

 public void zahl(ActionEvent evt)
         {
          int eZahl = Integer.parseInt(eingabe.getText()); // Einlesen Eingabe
          int pZahl = 2; // Primzahl?
          String aZahl = "2"; // Ausgabe
          
          while(pZahl < eZahl)
                 {

                 pZahl++;
                 double wurzel = Math.round(Math.sqrt(pZahl)); // Wurzel ziehen & runden
                 
                 
                 boolean prim = false;
                 while(wurzel > 1)
                        {
                        
                     
                        if(pZahl%wurzel != 0)
                            {
                            
                            prim = true;
                            
                            }
                        else
                            {
                            break;
                            }
                          
                        wurzel--;
                        
                        }
                 
                 if(prim)
                     {
                 
                     aZahl = aZahl+", "+Integer.toString(pZahl);
                 
                      }
                 
                 
                 }
          
          ausgabe.setText(aZahl); // Primzahlen ausgeben
          eingabe.setText("");
         }

Merci wapplegraph

 

[Skeeve]

              if(pZahl%wurzel != 0)
                            {
                            
                            prim = true;
                            
                            }

Da steht: Wenn pZahl nicht durch wurzel teilbar, dann ist das ganze prim. Stell Dir Nun eine Zahl vor, die durch den ersten Versuch nicht teilbar ist. Ergebnis: prim ist true. Im nächsten Versuch ist prim immer noch true. Wenn die Zahl nun aber kein Teiler ist, bleibt prim auf true!

Das nur als Denkanstoß.

Weiterhin finde ich unschön, die Wurzelfunktion zur Primzahlberechnung heranzuziehen. Wenn Du hochzählst und a / b = c rest d errechnest, hast Du auch schon die Abbruchbedingung, wenn nämlich b >= c ist. Und hier war keine Wurzelberechnung nötig.

Außerdem kann man dann bei 3 beginnen und in 2erschritten hochzählen.

Aber das sind nur Dinge, die Du gar nicht wissen wolltest....

 

[wapplegraph]

Ok Merci vielmals!

Es klappt nun. Und habe gleich alle Tipps umgesetzt.

Bin jetzt ganz offen für alle Tipps, wollte jedoch zuerst die Lösung für das direkte Problem.

Habe nun noch ein Problem mit der Ausgabe. ich gebe die Zahlen in ein Label aus. Es macht mir jedoch keinen Umbruch und so zeigt es mir nur eine Zeile an. Wie kann ich dies lösen?

Merci wapplegraph

 

[delycs]

Auch wenns nicht erwünscht war. Durch das Wurzelziehen büßt du einiges an Speed ein. Der Normale Weg wäre ein Modulo-Test:

int isprime(int n) {
    if          (n <  2) { return 0; }
    else if     (n == 2) { return 1; }
    else if (n % 2 == 0) { return 0; }
    else {
        for (int i=3; i*i<=n; i+=2) {
            if (n%i == 0){ return 0; }
        }
        return 1;
    }
}

Vorteil: Es werden die kleinen Teiler zuerst getestet. Die WKT bei großenZahlen früh abzubrechen ist also recht hoch.
Nachteil: Es muß für jede Zahl neu getestet werden.

daraus folgt ein weiterer Algo namens"Sieb des Eratosthenes"

char *arr = malloc(SIZE);

void primesieve(int len, char* arr) {
    memset(arr, 1, len);

    if (len > 0) arr[0] = 0;
    if (len > 1) arr[1] = 0;

    for (int i=4; i<len; i+=2) {
        arr[i] = 0;
    }

    for (int i=3; i*i<=len; i+=2) {
        if (arr[i]) {
            for (int j=2*i; j<len; j+=i) {
                arr[j] = 0;
            }
        }
    }
}

Dabei wird vorher ein Feld [0..MaxTestNumber] mit Nicht-Nullen angelegt. Beginnend mit 2 wird für alle Vielfache einer Primzahl, das entprechende Element auf Null gesetzt und der Zähler um Eins erhöht. Das nächste Element das Nicht-Null ist, ist wiederum eine Primzahl und alle Vielfachen werden Null gesetzt. usw...
Diese Schleife muß nur 'etwa bis zur Wurzel' (i*i<=len) der Feldlänge durchgeführt werden. (Hab leider keinen Beweis dafür gefunden :-0 )
Alle Primzahlen sind in diesem Feld nun mit einer 1 markiert.

Hab den Code irgendwo aus dem Netz. Ist zwar c, sollte aber in 10 minuten in java übersetzt werden können.