1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Primzahlen Algorithmus

Dieses Thema im Forum "Web-Programmierung" wurde erstellt von wapplegraph, 19.12.07.

  1. wapplegraph

    wapplegraph Normande

    Dabei seit:
    12.04.06
    Beiträge:
    571
    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?

    Code:
     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
     
  2. Skeeve

    Skeeve Pomme d'or

    Dabei seit:
    26.10.05
    Beiträge:
    3.121
    Code:
                  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....
     
  3. wapplegraph

    wapplegraph Normande

    Dabei seit:
    12.04.06
    Beiträge:
    571
    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
     
  4. delycs

    delycs Weigelts Zinszahler (Rotfranch)

    Dabei seit:
    13.09.06
    Beiträge:
    245
    Auch wenns nicht erwünscht war. Durch das Wurzelziehen büßt du einiges an Speed ein. Der Normale Weg wäre ein Modulo-Test:
    Code:
    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"
    Code:
    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.
     

Diese Seite empfehlen