Home | Registrieren | Mitgliederliste | Suchen | Hilfe | Themen des Tages | Alle Lampen aus | Login
Guten Tag, Gast

Wenn dies Dein erster Besuch hier ist, lies Dir die FAQ - Häufig gestellte Fragen durch. Du musst Dich vermutlich Registrieren, bevor Du Beiträge schreiben kannst: klicke oben auf registrieren, um den Registrierungsprozess zu starten. Um Beiträge zu lesen, suche Dir einfach das Forum aus, das Dich interessiert. Die Registrierung ist kostenlos.
Username:
Passwort:
Suchen:


Seiten: <<  1  >>
Board >>  Theorien >>  Ansaetze >> schnellste Methode alle Primzahlen zu ermitteln
Neues Thema    »Antworten«
Seite Drucken
red.gif Autor:
Thema: schnellste Methode alle Primzahlen zu ermitteln
psychocoder (offline)
Newbie



Beiträge: 5
Geschlecht:
Mitglied seit: 20.09.2007

Deutschland
icon1   schnellste Methode alle Primzahlen zu ermitteln #1 Datum: 20.09.2007, 16:44  


Hallo @ll,

ich bin neu hier im Forum und würd gern Erfahrungen austauschen.

Welche Methode ist die schnellste alle Primzahlen von 2-X zu berechnen??

Ich habe zur Zeit 3 Methoden getestet in C mit einem AMD X2 3600+ 2GB RAM:

Sieb des Eratosthenes: (von 2-100.000.000) Dauer 4290ms

meine Methode: (von 2-100.000.000) Dauer ca. 3429ms

abgewandeltes Summenverfahren (von 0 - 1.000.000) Dauer ca. 8147ms
(s.hier) Dauer langsamer
Dabei muß ich erwähnen das das letzte Verfahren viel weniger Speicher braucht, was aber erstmal egal ist. Es wurde von mir auch nicht so Programmiert wie auf wie auf der Homepage beschrieben.

Kennt jemand noch ein sehr schnelles Verfahren zum Berechnen aller Primzahlen im Zahlenbereich. Wenn ja wär ein C Code sehr schön damit ich ihn mit den andern Methoden vergleichen kann.
   PM   Buddy hinzufügen Copy Quote
psychocoder (offline)
Newbie



Beiträge: 5
Geschlecht:
Mitglied seit: 20.09.2007

Deutschland
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #2 Datum: 20.09.2007, 18:36  


Ich hoffe es kann mir jemand einen schnellen Algorithmus nennen oder gar einen C/C++ Code Posten!!
   PM   Buddy hinzufügen Copy Quote
psychocoder (offline)
Newbie



Beiträge: 5
Geschlecht:
Mitglied seit: 20.09.2007

Deutschland
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #3 Datum: 21.09.2007, 15:48  


OK mein eigenes Verfahren welches auf dem Sieb des Eratosthenes basiert konnte ich nun verschnellern und es läuft von (0-100.000.000) in 804 ms. Das gute ist nun ich kann danach alle Zahlen im Zahlenbereich Faktorisieren (dauert nicht mal eine ms).

Nun komm ich aber wie alle Methoden die auf dem Sieb basieren an Speichergrenzen (RAM zu klein) und brauche paar gute Tipps wie man Primzahlen speicherschonend und schnell berechnen kann!
Ich hab jetzt eine Version mit Listen geschrieben was allerdings langsam ist, dafür aber speicherschonend. Was kann ich nun noch probieren??
   PM   Buddy hinzufügen Copy Quote
psychocoder (offline)
Newbie



Beiträge: 5
Geschlecht:
Mitglied seit: 20.09.2007

Deutschland
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #4 Datum: 21.09.2007, 15:50  


So nun der erste Code zum Sieb:
code:
void primesieve(int len, char* arr) {
   

    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;
            }
        }
    }
}

code:
char *arr;
        int time;

        QTime t;
        int end;
       
        if(argc>1)
                 end=atoi(argv[1]);

        arr=(char*) malloc(end);
    memset(arr, 1, end);
   
    t.start();
    primesieve(end, arr);
    time=t.elapsed();

    cout<<"Found in ms "<<time<<endl;

        free(arr);
   PM   Buddy hinzufügen Copy Quote
psychocoder (offline)
Newbie



Beiträge: 5
Geschlecht:
Mitglied seit: 20.09.2007

Deutschland
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #5 Datum: 21.09.2007, 15:51  


Und nochmal meine Umsetziung zum Summenverfahren.

code:
int *a,*b,end,time;
        int i,j,j_end=0,sem=1;
        QTime t;
       
        if(argc>1)
                 end=atoi(argv[1]);
       
        a=new int[end];
        b=new int[end];
       
        for(i=0;i<end;i++){
                a[i]=0;
                b[i]=0;
        }
       
        t.start();
        i=3;
        while(j_end<end){
                sem=1;
                for(j=0;j<j_end;j++){
                        while(a[j]<i)
                                a[j]+=(b[j]<<1);
                        if(a[j]==i){
                                sem=0;
                                break;
                        }
                }
                if(sem){
                        b[j_end]=i;
                        a[j_end]=i+(i<<1);
                        j_end++;
                }
                i+=2;
        }
        time=t.elapsed();
        //for(i=0;i<end;i++)
                //cout<<b[i]<<endl;
        cout<<"Found in ms "<<time<<endl;


        delete[] a;
        delete[] b;
   PM   Buddy hinzufügen Copy Quote
Triton (offline)
Newbie



Beiträge: 21
Geschlecht:
Mitglied seit: 17.08.2006

Deutschland
 
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #6 Datum: 18.10.2007, 20:16  


Naja, das ist ja ganz schön und ich kann verstehen, welche freude es bereitet, einen schönen, hochoptimierten Algorithmus zu schreiben.

Aber als zweites fragt man sich, wozu das ganze?

Ich habe auch mal ein Primzahlprogramm (ach, nicht nur eins, dutzende ;)) geschrieben, dass einfach alle Pz nacheinander ausgibt.
Bei 2^31 - 1 habe ich aufgehört. Bis dahin waren es glaube ich so 800 MB.
       PM   Buddy hinzufügen Copy Quote
Cybertronic (offline)
Newbie



Beiträge: 14

Mitglied seit: 14.11.2006

Deutschland
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #7 Datum: 19.10.2007, 23:54  


Ich kann nicht erkennen , weiß die schnellere Methode ist.
Schneller als Sieb des E. geht: Man arbeitet mit Mustern. Man bildet z.B. den Stemel: 2*3*5*7*11*13*17*19=9699690: Und speichert alle Zahlen im festen Feld 0 bis 9699690 mit Teiler 2,3,5,7,11,13,17,19 als "belegt".
Obergrenze für Teiler zum Sieb ist (9699690*x)^0.5 und beginnt immer mit der Primzahl 23. Für ein 2. Feld beginne mit 23 ,29..., Vergleiche dann ob Feld 1 und 2 keine Teiler haben. Die Primteiler fürs sieb würde ich vorher berechnen.


     PM   Buddy hinzufügen Copy Quote
Cybertronic (offline)
Newbie



Beiträge: 14

Mitglied seit: 14.11.2006

Deutschland
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #8 Datum: 20.10.2007, 00:02  


Quasi könnte man mit einem 2 Feldern a 10MIO bis ultimo die PZs rechnen.
Ich selber such nach einem 13 Tupel mit 45 Stellen. Mit der gegebenen Struktur gibs 1 Exemplar zwischen 0 und 300000000000000 fürdie relevanten Faktoren f der Form f*x#+y . Aber das ist ein anderes Kapitel.
Nur kann man geschickt über die 2^31 locker hinaussieben, mit einem minimalen Feld.
     PM   Buddy hinzufügen Copy Quote
Daun (offline)
Newbie



Beiträge: 8
Geschlecht:
Mitglied seit: 09.09.2006

Schweiz
icon1   Re: schnellste Methode alle Primzahlen zu ermitteln #9 Datum: 18.03.2008, 20:09  


Ich hab da auch mal noch ein Programm geschrieben:

Programm
Quelltext
   PM   Buddy hinzufügen Copy Quote
Board >>  Theorien >>  Ansaetze >> schnellste Methode alle Primzahlen zu ermitteln
Seiten: <<  1  >>
Seite Drucken
Neues Thema    »Antworten«



Forum durchsuchen:


   


Stefanos Bulletin Board, v1.3.7
© Coder-World.de, 2001-2005 (Stefanos)