PrimzahlenTest

  • C Quelltext: http://pastebin.com/YzChJUjA (Wer es schöner haben möchte...)
    Wer mag kann ja testen und dann sagen wieviele er in wieviel zeit gefunden hat.

    [Blockierte Grafik: http://bktm.ron-welzel.de/Download/C/Primzahlen/primzahlen_2_999999999.png]

    Spoiler anzeigen


    #include <stdio.h>
    #include <stdlib.h>
    #include <Windows.h>
    #include <limits.h>

    #define DATENTYP unsigned long int

    short eratosthenes(char *nListe, DATENTYP nGrenze)
    {
    unsigned long long i, nPrimteiler = 2, q;

    if (nGrenze < 2) return 0;

    for (i = 2; i < nGrenze; i++)
    {
    nListe = 1;
    }

    while (nPrimteiler*nPrimteiler < nGrenze)
    {
    q = 2;
    while (q*nPrimteiler < nGrenze)
    {
    nListe[q*nPrimteiler] = 0;
    q++;
    }

    do
    {
    nPrimteiler++;
    } while (nListe[nPrimteiler] == 0);
    }

    return 1;
    }


    double get_time()
    {
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart / (double)f.QuadPart;
    }

    int main(int nArgs,char **szArgs) {


    DATENTYP nAnzahl = 999999999, i, nCounter = 0;
    short bIsOk = 0;
    double dStart,dEnd;
    char *pnListe = (char*)malloc(nAnzahl * sizeof(char));
    dStart = get_time();
    bIsOk = eratosthenes(pnListe, nAnzahl);
    dEnd = get_time();
    if (bIsOk == 1)
    {

    for (i = 2; i < nAnzahl; i++)
    {
    if (pnListe == 1)
    {
    //printf_s("%i ist eine Primzahl.\n", i);
    nCounter++;
    }
    }
    }
    printf_s("\n%lf Sekunden um von 2 bis %u Primzahlen zu finden.\nGefundene Primzahlen: %u\n\n", dEnd - dStart, nAnzahl, nCounter);
    free(pnListe);

    }


  • Hier ein bisschen Feedback/Wüsche:
    Erstmal hast du zwar ohne Kommentare programmiert, aber auch ohne C Kenntnisse konnte ich die Idee deines Skriptes ganz gut nachvollziehen.
    (Selbst wenn ich das Sieb des Eratosthenes nicht bereits gekannt hätte)
    Ich bin zwar keineswegs mit C vertraut, aber dein Sieb des Eratosthenes hätte doch auch in einer Liste von Wahrheitswerten implementiert werden können und dadurch einen kleinen Geschwindigkeitsboost bekommen können, oder?
    Als Erweiterung könntest du ja die Liste in k viele Teile teilen, die von k Threads bei jedem "Sieben" je ein Stück aktualisieren.
    Ich habe den Code zwar nicht getestet, war aber von dem Titel angetan (...), da ich aber keine Liste aller Primzahlen von 2 bis n brauche und von C so gut wie keine Ahnung habe,
    würde ich dich um folgendes Features bitten:
    Eine Funktion IsPrime(x) : boolean, die auf Primzahlen prüft.
    D.h. man kann eine beliebige natürliche Zahl auf ihre Primzahleneigenschaft prüfen. Dazu fallen mir spontan 2 Verfahren ein:
    AKS-Primzahltest (nicht probabilistisch soweit ich weiß und daher hilfreich für mich)
    Miller Rabin Test (probabilistisch)
    *weitere, möglichst effiziente(re) Verfahren die nicht probabilistisch sind fänd ich auch gut*
    Der naive Ansatz die Zahl x auf alle Teiler < WurzelAus(x) dauert viel zu lange, wenn die Primzahl ca. 100 Stellig (<=>10^100) ist.
    Ich würde es Klasse finden, wenn du das mal in C probieren könntest :)

    Wer immer nur das tut, was er bereits kann - wird auch immer nur das bleiben, was er bereits ist!

  • doch auch in einer Liste von Wahrheitswerten implementiert werden können und dadurch einen kleinen Geschwindigkeitsboost bekommen können, oder?

    Das Problem ist das c kein Boolean an sich als datentyp hat.
    Nur von MS z.b. die Definition.
    in C++ schon.

  • Hehe :D
    Oder einfach so:

    AutoIt

    [autoit]

    Func IsPrime($x)
    If Not IsNumber($x) Then Return False
    If $x < 2 Then Return False
    If $x - Int($x) Then Return False
    For $i = 2 To $x -1
    If Not Mod($x, $i) Then Return False
    Next
    Return True
    EndFunc

    [/autoit]

    C++

    Code
    bool IsPrime(unsigned long long x) {
    	if (x < 2) {return false;}
    	for (unsigned long long i = 2; i < x -1; i++) {
    		if (!(x % i)) {return false;}
    	} return true;
    }

    Jede Zahl von 2 bis x einfach mit der Funktion prüfen und schon hat man seine Primzahl. Dauert aber demnach auch länger... ^^

  • Kannst du mir das bitte näher erläutern?


    Ok, nehmen wir als Beispiel 40. Die Grenze wäre in diesem Fall 7.
    40 / 8 = 5 R 0 ; brauchst du aber nicht überprüfen, da du die 5 schon überprüft hast
    40 / 10 = 4 R 0 ; brauchst du auch nicht überprüfen, da du die 4 schon überprüft hast
    40 / 20 = 2 R 0 ; brauchst du auch nicht überprüfen, da du die 2 schon überprüft hast
    ...

    Man könnte also sagen, dass sich die Überprüfungen an der Grenze spiegeln. Ist nicht gerade gut erklärt aber ich hoffe du verstehst was ich meine.

  • Hi,
    zunächst: ich war total stolz den o.a. Code in VC++ mit kleinen Änderungen zum Laufen (und compiliert) bekommen zu haben^^

    Was soll man sagen...C halt...der Code ist 4x langsamer als mein unoptimiertes Assemblerstück, dass sogar noch sämtliche Primzahlen in eine Datei schreibt...

    Spoiler anzeigen
    [autoit]

    ;Liste der Primzahlen bis $maximum
    ;32-Bit Bytecode by Andy, eine der ersten Versionen, daher unoptimiert und "langsam"

    [/autoit] [autoit][/autoit] [autoit]

    Local $maximum = 1299709 ;Obergrenze der Primzahlen
    Local $file = "Prim_" & $maximum & ".au3" ;Datei, in welche die Primzahlen geschrieben werden

    [/autoit] [autoit][/autoit] [autoit]

    $t = TimerInit() ;Timestamp sichern
    $tStruct = DllStructCreate("uint Limit;uint Limes;char Mem[" & $maximum + 10 & "]") ;char, dann kann man nachher schön mit den stringfunktionen suchen
    ;die folgenden 4 Zeilen sparen einige Zeilen Assemblercode, außerdem kann man sich den Speicherinhalt in AutoIt anschauen
    DllStructSetData($tStruct, "Mem", "001") ;die ersten 3 Zahlen setzen, 0=0 1=0 2=1 , 2 ist die erste Primzahl
    DllStructSetData($tStruct, "Limit", $maximum);limit in die Struct schreiben
    DllStructSetData($tStruct, "Limes", Floor(Sqrt($maximum)) + 1);wurzel aus limit in die struct schreiben
    $bytecode = "0x558B6C24088B5D00B803000000C74405083130313083C00439D876F189EF83C70889FE8B4D00BB0300000089D8F7E0C604063001D839C87CF683C3023B5D007737803C1E3175F2535189D8BB0A00000031C931D2F7F3665280C10109C075F366580C30AAE2F9C6070D83C701595B3B5D047CB83B5D007CC1C607005DC3"
    $tCodeBuffer = DllStructCreate("byte[" & StringLen($bytecode) / 2 & "]") ;Speicher für den bytecode reservieren...
    DllStructSetData($tCodeBuffer, 1, $bytecode);...und mit dem Bytecode beschreiben
    ;die folgende Zeile startet den bytecode im Speicher und kehrt danach hierher zurück
    $t = TimerInit() ;Timestamp sichern
    $a = DllCall("user32.dll", "int", "CallWindowProcW", "ptr", DllStructGetPtr($tCodeBuffer), "ptr", DllStructGetPtr($tStruct), "int", 0, "int", 0, "int", 0);bytecode aufrufen, rückgabe in a[0]

    [/autoit] [autoit][/autoit] [autoit]

    $primzahlen = "2" & @CR & "3" & @CR & DllStructGetData($tStruct, "Mem");2 und 3 sind die ersten Primzahlen, dann folgt der Rest
    $m = TimerDiff($t) ;Zeit seit Programmstart

    [/autoit] [autoit][/autoit] [autoit]

    FileDelete($file) ;Primzahldatei löschen
    FileWrite($file, $primzahlen) ;Ausgabe der Primzahlen in Datei
    $m1 = TimerDiff($t);Zeit seit Programmstart incl Datei schreiben

    [/autoit] [autoit][/autoit] [autoit]

    StringReplace($primzahlen, @CR, @CR, 0, 1) ;alle CR im String zählen.....auch AutoIt hat SPEEEEED^^
    $anzahlprim = @extended ;hätte man auch vom Assembler zurückgeben lassen können^^

    [/autoit] [autoit][/autoit] [autoit]

    MsgBox(262144, "Primzahlen bis " & $maximum, $anzahlprim & " Primzahlen ermittelt in " & Int($m) & " Millisekunden" & @CRLF & _
    "Primzahlen ermitteln und in Datei schreiben in " & Int($m1) & " Millisekunden." & @CRLF & _
    "Ausgabe der Zahlen folgt in die Datei " & $file & @CRLF & _
    "Die Primzahldatei wird nun angezeigt...")
    ShellExecute($file) ;in Scite anzeigen

    [/autoit]


    Mit einem (so wie hier beschrieben) modifizierten Sieb ist nochmal Faktor 3-4 in der Geschwindigkeit drin...

    Btw. früher gab es mal den µ-It (auch als light-Version) hier im Forum, um Primzahlen und Scripte ging es im angehängten Link, viel wichtiger sind die vorgestellten Algorithmen, die entsprechend umgesetzt Welten schneller in einer Compilersprache laufen http://www.autoit.de/index.php?page=Thread&postID=141580#post141580

    ciao
    Andy


    "Schlechtes Benehmen halten die Leute doch nur deswegen für eine Art Vorrecht, weil keiner ihnen aufs Maul haut." Klaus Kinski
    "Hint: Write comments after each line. So you can (better) see what your program does and what it not does. And we can see what you're thinking what your program does and we can point to the missunderstandings." A-Jay

    Wie man Fragen richtig stellt... Tutorial: Wie man Script-Fehler findet und beseitigt...X-Y-Problem

    3 Mal editiert, zuletzt von Andy (25. November 2013 um 20:12)

  • Andy, guter Code

    Sie können darum bitten, den gleichen Code zu erstellen, um die Zahl in Primfaktoren zu verteilen

    1232334646758235345 ==> 5*13*2131*1942141*4580903

    948013690567935577 ==> 948013690567935577

  • Oder so prüfen:

    Spoiler anzeigen

    Lieben Gruß,
    Alina

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Geheime Information: ;)
    OuBVU5ebLhHu5QvlnAyQB4A7SzBrvWulwL7RLl2BdH5tI6sIYspeMKeXMSXl

  • Alina, Warum zeigst du mir das - dein Code funktioniert nicht mit großen Zahlen

    EDIT BugFix: [Link entfernt]

    Or GMP "__gmpz_probab_prime_p"

    Die Frage war, wie man für große Zahlen

    1232334646758235345 ==> 5*13*2131*1942141*4580903


    948013690567935577 ==> 948013690567935577

    2 Mal editiert, zuletzt von Andrey_A (20. März 2023 um 15:56)

  • Aber für große Zahlen funktioniert es nicht.

    Einmal editiert, zuletzt von Andrey_A (20. März 2023 um 16:00)

  • Folgendes habe ich aus einem Uni-Bereich rausgezogen.

    n < 1.373.653 : es genügt, a= 2 und 3 zu testen,

    n < 9.080.191 : es genügt, a = 31 und 73 zu testen,

    n < 4.759.123.141 : es genügt, a = 2, 7, und 61 zu testen,

    n < 2.152.302.898.747 : es genügt, a = 2, 3, 5, 7, und 11 zu testen,

    n < 3.474.749.660.383 : es genügt, a = 2, 3, 5, 7, 11, und 13 zu testen,

    n < 341.550.071.728.321 : es genügt, a = 2, 3, 5, 7, 11, 13, und 17 zu testen.

    n < 3.825.123.056.546.413.051 : es genügt, a = 2, 3, 5, 7, 11, 13, 17, 19, und 23 zu testen.

    n < 318.665.857.834.031.151.167.461 : es genügt, a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 zu testen.

    Dabei dürfen nur solche n getestet werden, die größer sind als das jeweils größte a !!

    Lieben Gruß,
    Alina

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Geheime Information: ;)
    OuBVU5ebLhHu5QvlnAyQB4A7SzBrvWulwL7RLl2BdH5tI6sIYspeMKeXMSXl