Primzahlen berechnen - Wieso unterschiedliche

[Baunty]

Hallo Community,

ich bin gerade mehr aus langeweile dabei das Primzahlen Programm das ich geschrieben habe zu optimieren...
Ich bin auch schon relativ weit gekommen von dem 1. Entwurf bis jetzt ist es ca. 100 mal so schnell xD naja die erste version war auch unzumutbar :bae:

Jedenfalls habe ich eine Frage die ich mir einfach nicht erklären kann da sie aus Mathematischer und somit für mich auch logischer Sicht einfach so nicht sein kann.
Ich habe z.Z. diesen funktionierenden Quellcode :

private void berechnePrimzahlenNeu(int bis) {
        
        int i, j, z, anzahlprimzahlen=5;
        long begin = System.currentTimeMillis();
        long dif;
        
        int [] prim = new int[bis];
        
        
        //System.out.println("1");
        System.out.println(prim[0] = 1);
        System.out.println(prim[1] = 2);
        System.out.println(prim[2] = 3);
        System.out.println(prim[3] = 5);
        System.out.println(prim[4] = 7);
        
        
        
        for(i = 8; i<bis; i++) {
            
            z=0;

            for(j=0 ; j<anzahlprimzahlen;j++) {
                if (prim[j] < i / 2) {
                    if (i % prim[j] == 0) {
                        z++;
                        if (z > 1) {
                        break;
                        }
                    }
                }
            }
        
            
            if(z==1) {
                prim[anzahlprimzahlen++] = i;
                System.out.println(i);
            }
            
            
        }
        
        long ende = System.currentTimeMillis();
        dif = (ende - begin) / 1000;
        this.ausgabe(bis, anzahlprimzahlen, dif);
    }
    
    
    
    private void ausgabe(int grenze, int anzahl, long dif) {
        System.out.println("----------------------------");
        System.out.println("Bis " + grenze + " gibt es " +  anzahl  + " Primzahlen");
        System.out.println("Dauer : " + dif + " Sekunden");
    }

Die Ausgabe bei einem Parameter von 1 Millionen ist :

... alle primzahlen...
...
----------------------------
Bis 1000000 gibt es 78499 Primzahlen
Dauer : 50 Sekunden

Das Programm kontrolliert jetzt aber so das es die z.Z. behandelte Zahl durch alle Primzahlen teilt, also alle bisherigen Werte im prim array.
Der 1. Wert ist hier nunmal 1, durch 1 geteilt ergibt keinen Rest also wird z, die Variable die die Anzahl der Treffer zeigt, um eins hoch gezählt.
Sobald z nen 2. mal hochgezählt wird ist Ende und die behandelte Zahl ist keine Primzahl.
Den Schritt müsste ich doch überspringen können und einfach mit 2 Anfangen indem ich die for-schleife von j entweder mit 1 beginnen lasse oder das Primzahlen Array nicht mit 1 sondern mit 2 anfangen lasse...
aber egal wie ichs mach bei beidem kommt folgende Ausgabe :

----------------------------
Bis 1000000 gibt es 771427 Primzahlen
Dauer : 1390 Sekunden

Neuer Quellcode wäre :

 for(i = 8; i<bis; i++) {
            
            z=0;

            for(j=1 ; j<anzahlprimzahlen;j++) {
                if (prim[j] < i / 2) {
                    if (i % prim[j] == 0) {
                        //z++;
                        //if (z > 1) {
                        prim[anzahlprimzahlen++] = i;
                        System.out.println(i);
                        break;
                        //}
                    }
                }
            }
           
            /*
            if(z==1) {
                prim[anzahlprimzahlen++] = i;
                System.out.println(i);
            }
            */
            
        }

Kann mir das wer bitte erklären ich versteh´s einfach nicht ;-)

 

[Baunty]

Mein neuer Code zählt ja jedes mal Hoch wenn der Rest 0 ist das ist ja ganz falsch :shock:

 inner:
        for(i = 8; i<bis; i++) {
            
            z=0;

            for(j=1 ; j<anzahlprimzahlen;j++) {
                if (prim[j] < i / 2) {
                    if (i % prim[j] == 0) {
                        continue inner;
                    }
                }
            }
            prim[anzahlprimzahlen++] = i;
            System.out.println(i);
        }

So aber der hier braucht trotzdem 50 Sekunden obwohl ich 2 if Abfragen spare..
bringt das denn garnichts?

 

[Wildcard]

ifs sind billig. Der Algorithmus ist einfach schlecht.
Nicht der schnellste, aber einfach zu implementieren und wesentlich schneller als deine Variante:
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

 

[Marco13]

Ich glaube, das war das, was er versucht hatte
Das Programm kontrolliert jetzt aber so das es die z.Z. behandelte Zahl durch alle Primzahlen teilt, also alle bisherigen Werte im prim array.
???:L
Aber... wer weiß....