kostenloser Webspace werbefrei: lima-city


Primzahlen

lima-cityForumProgrammiersprachenDelphi & Pascal

  1. Autor dieses Themas

    morph01

    morph01 hat kostenlosen Webspace.

    Hey, Ich brauche einen Denkanstoß: Wie bestimme ich, ob eine Zahl eine Primzahl ist :D?
    Vielen Dank für eure Mühe schonmal ;)
    Morph01
  2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

    lima-city: Gratis werbefreier Webspace für deine eigene Homepage

  3. burgi

    Co-Admin Kostenloser Webspace von burgi

    burgi hat kostenlosen Webspace.

    Dazu liefert Wikipedia ein recht gutes Ergebnis:
    http://de.wikipedia.org/wiki/Primzahltest

    Wähle einen entsprechenden Algorithmus, und implementiere ihn. Viel Spaß dabei :wink:

    Hier findest du eine fertige, einfache Implementierung:
    http://www.programmersheaven.com/mb/delphikylix/294826/294826/prime-numbers-help/
  4. Du iterierst durch alle Zahlen, deren Quadrat kleiner ist als die zu prüfende Zahl. Am besten Anfangen mit 1 und in Zweierschritten, damit du die ganzen geraden Zahlen nicht machen musst. Dann siehst du ob die zu bestimmende Zahl modulo die Zahl, die gerade bei der Iteration entsteht, 0 ist. (Hoffe das war verständlich. Sonst nachfragen :))

    Pseudocode:
    while(i=3;i*i<Z;++i) {
    if(!Z%i) {
    return false;
    }
    }
    return true;


    Beitrag zuletzt geändert: 21.10.2009 19:39:04 von nikic
  5. Autor dieses Themas

    morph01

    morph01 hat kostenlosen Webspace.

    Also wäre es in etwa soetwas:
    procedure TForm1.isprim(Zahl:integer):boolean
    var i,wurz:integer;
    begin
    wurz:=Trunc(sqrt(Zahl));
    for i:=2 to wurz do begin
    if zahl/i0Trunc(Zahl/i) then resut := true;
    end;
    end;
  6. c****s

    Wie groß sind denn die Zahlen, die du prüfen willst?
    Und: mit welcher Sicherheit soll der Test eine Primzahl als solche erkennen und wie groß dürfen die Fehler erster und zweiter Art sein?

    Hier ein paar Denkanstöße:
    - Fermat-Test,
    - Miller-Rabin-Test,
    - Solovay-Strassen-Test,
    - ECPP (mein Favorit).

    Primzahlentests sind ja eines der großen Steckenpferde der Informatik und hier noch ein interessanter Fetzen aus Wiki:
    Die den Primzahltest zugrundeliegende Problemstellung, festzustellen, ob eine Zahl prim ist, wird in der Informatik als PRIMES bezeichnet. Bis ins Jahr 2002 erhoffte man sich in der Komplexitätstheorie von ihr neue Erkenntnisse in Bezug auf das P-NP-Problem. Falls P≠NP gilt, muss nach dem Satz von Ladner ein Problem in NP\P existieren, welches nicht NP-vollständig ist[1]. PRIMES galt als ein potenzieller Kandidat für ein solches Problem.

    Dies lag daran, dass PRIMES sowohl in der Komplexitätsklasse NP als auch in der Komplexitätsklasse co-NP liegt, und demnach nicht NP-vollständig sein konnte. Man kannte jedoch keinen nicht-probabilistischen Lösungsalgorithmus mit polynomieller Laufzeit. Daher war es fraglich, ob PRIMES auch in der Komplexitätsklasse P liegt.

    2002 wurde jedoch von Agrawal, Kayal und Saxena mit dem AKS-Primzahltest ein solcher polynomieller Primzahltest gefunden. Damit war die lange Zeit offene Frage, ob PRIMES in P liegt, beantwortet. Dies brachte jedoch keine weitere Erkenntnis zum P-NP-Problem.


    EDIT:
    nikic schrieb: Du iterierst durch alle Zahlen, deren Quadrat kleiner ist als die zu prüfende Zahl. Am besten Anfangen mit 1 und in Zweierschritten, damit du die ganzen geraden Zahlen nicht machen musst. Dann siehst du ob die zu bestimmende Zahl modulo die Zahl, die gerade bei der Iteration entsteht, 0 ist. (Hoffe das war verständlich. Sonst nachfragen :))
    morph01 schrieb: Also wäre es in etwa soetwas:
    procedure TForm1.isprim(Zahl:integer):boolean
    var i,wurz:integer;
    begin
    wurz:=Trunc(sqrt(Zahl));
    for i:=2 to wurz do begin
    if zahl/i0Trunc(Zahl/i) then resut := true;
    end;
    end;

    Das Problem hier ist, dass das nur bis MAX_INT geht, also 2^64 wahrscheinlich, abhängig von der Architektur. Interessante und relevante Primzahlen, z.B. für Kryptoalgorithmen, sind leider ein bisserl größer.

    Beitrag zuletzt geändert: 21.10.2009 19:40:00 von census
  7. Autor dieses Themas

    morph01

    morph01 hat kostenlosen Webspace.

    Jaja klar, ich brauche etwas genaues, und Zahlen über 2^64 werde ich wohl nicht testen ;)
    Und Primzahlen generieren - soll ich einfach in Zweierschritten hochzählen und mit meiner Prozedur jede einzelne Primzahl testen? Oder gibt es dafür andere Algorythmen?
  8. @census: Du glaubst nicht, das jemand, der hier im Forum danach fragt, Primzahlen in kryptografischer Höhe berechnen möchte... (das wusstest du aber auch ohne dass ich es dir sage)

    @morph: Zumindest ist es das einfachste und das offensichtlichste.
  9. Autor dieses Themas

    morph01

    morph01 hat kostenlosen Webspace.

    mhm... Aber die Performance (für meine Anwendung wichtig) ist wahrscheinlich relativ schlecht...
    und wenn ich dann mal über die Integer-Grenzen stoße, werde ich mich an Census Beitrag erinnern und int64 oder so nehmen
    (Welcher Variablentyp war nochmal nur Positiv? Cardinal oder so?)
    Dankeschön für dei schnellen und vielen Antworten, ihr habt mir sehr geholfen ;)
    morph01
  10. c****s

    morph01 schrieb:
    mhm... Aber die Performance (für meine Anwendung wichtig) ist wahrscheinlich relativ schlecht...
    und wenn ich dann mal über die Integer-Grenzen stoße, werde ich mich an Census Beitrag erinnern und int64 oder so nehmen
    (Welcher Variablentyp war nochmal nur Positiv? Cardinal oder so?)
    Dankeschön für dei schnellen und vielen Antworten, ihr habt mir sehr geholfen ;)
    morph01

    Auf heutigen Maschinen, kann die Performance um einen Integer auf Primalität zu testen gar nicht schlecht sein. Die empfohlene Brute-Force-Methode mit Ausprobieren jeder ungeraden Zahl bis zur Wurzel des Kandidaten hat den Aufwand O = n, ist also linear. Auf aktueller Hardware (und auch 4 Jahre alter Hardware) dürftest du da kaum die Laufzeit bemerken.
  11. Autor dieses Themas

    morph01

    morph01 hat kostenlosen Webspace.

    Naja, 15 Sekunden rattert das Programm aber schon mit voller Rechenleistung wenn ich von 1-1000000 teste ;)
  12. burgi

    Co-Admin Kostenloser Webspace von burgi

    burgi hat kostenlosen Webspace.

    morph01 schrieb:
    (Welcher Variablentyp war nochmal nur Positiv? Cardinal oder so?)

    So ist es, hier eine Auflistung sämtlicher Datentypen:
    http://www.epinasoft.com/delphikurs/dkk_datatypes.html
  13. ich hätte da eine Methode, dass Primzahlen bis 1000000 in einer Sekunde gerechnet wird... auf einem Pentium 1...

    es gibt einen trick:du fängst bei 2 an... die beiden drunter kansnt du so hinschreiben, als anfangsbedingungen...
    eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...


    dann ermittelst du mithilfe dieser Primzahlen die nächste Primzahl durch rechnen mit den anderen Primzahlen. das wäre die 3.
    Die schreibst du dann in eine Matrix. diese enthält {2, 3}.

    So, jetzt läufst du das oben nochmal durch. Die 4. dann nimmt er die erste Zahl in der Matrix, also die 2, teilt die dadurch und weil rest 0 ist, bricht er die schleife ab und fährt mit

    der 5 fort. die 5 teilt er durch die erste zahl in der Matrix, also die 2. so, rest bleibt... also würde er jettzt die nächste Zahl nehmen... aber da die 3 größer als 5/2 ist, bricht er ab und erklärt die 5 gleich als primzahl...

    so, bei der 6 passiert dasselbe, wie bei der 4

    bei der 7 würde er die 3 als letztes prüfen, da sie kleiner als 7/2 ist, aber die 5 würde er auslassen und sofort die 7 als Primzahl definieren.


    und das würde immer so weiter gehen.

    Ich schreib dir das mal als pseudocode hin, falls du es in Delphi nciht realisieren kannst, helf ich dir da gerne weiter...

    int xMax=1000000;                         # kannst du auch über eine funktion übergeben... oder als zeiger... der wert wird nciht geändert
    int PrimMatrix[abs(xMax/2)+1];     # abs ist eine Funktion die den absoluten wert angibt, alsso die nachkommastellen abschneidet
    PrimMatrix[0]=2;
    int zaehler=3;      #->diese Variable soll bis zum letzten Wert hochzählen, der auf Primzahl geprüft wird
    int aktPrim=0;           #->diese Variable soll den Index der Matrize hochzählen, in 1er Schritten(index in matrix)
    int lastPrim=0;  #dieser wert zählt den index der letzten bekannten Primzahl
    for(zaehler;zaehler<=xMax;zaehler++)
    {
        for (aktPrim;aktPrim<=lastPrim;aktPrim++)
        {
           if(aktPrim == lastPrim)
            {
                lastPrim++;
                PrimMatrix[lastPrim]=zaehler; 
             }
              if(zaehler%PrimMatrix[aktPrim] == 0)
                {
                       break;
                 }
         }
    }
    
    # so und die Ausgabe kannst du machen wie bisher...  du kansnt es in eine tabelle hauen...  um das ganze sauber zu machen, sollteast du die komplette matrix in eine neue Matrix schreiben, die so groß ist, wie --->lastPrim+1<---  und dann darstellen , wie es dir beliebt...



    so, wenn du das ungefähr so umsetzt, dann kannst du primzahlen bis ewig rechnen, ohne dass dein rechner außer Puste gerät... musst natürlich schauen, wie die Begrenzung für Matrizen ist... ander nennen den Datentyp Felder... ist aber mehr so ein Wessi-Begriff...




    edit: hab kleine Verbesserung am Pseudocode vorgenommen

    Beitrag zuletzt geändert: 22.10.2009 19:04:24 von sebulon
  14. sebulon schrieb:

    eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...



    ich bin zwar nicht der fragesteller, aber mich interressiert trotzdem, warum man das machen kann??
  15. ganz einfach:

    bei Primzahlen handelt es sich doch um zahlen, die nur durch 1 und sich selbst teilbar sind. und alle teiler sind ganzzahlen.

    so, man kann eine Zahl in Primärfaktoren zerlegen. nehmen wir die 60. Die setzt sich zum beispiel aus folgenden Kombinationen zusammen:

    2 - 30
    3 - 20
    4 - 15
    5 - 12
    6 - 10

    so, da 2 immer der kleinstmögliche teiler ist, steht dem die größtmögliche Zahl gegenüber. in diesem Fall die 30

    aber die würde nciht erreicht werden, da das programm bei 2 aufhört, weil keine primzahl vorhanden ist...

    und so ist das immer... wenn was durch 2 teilbar ist, was bei 50% aller fälle ist, wird bei den Zahlen immer nur 1 Prüfung durchgeführt... und dann hat sich der Fall erledigt... lustig wird es im 5 stelligen bereich, wenn sich aus irgendeiner 4-stelligen primzahl was zusammensetzt oder aus 2 3-stelligen primzahlen...
  16. c****s

    t-li schrieb:
    sebulon schrieb:

    eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...



    ich bin zwar nicht der fragesteller, aber mich interressiert trotzdem, warum man das machen kann??

    Die Einschränkung ist richig und kann noch verstärkt werden, denn es reicht bis zur Quadratwurzel des Kandidaten zu testen und nicht bis zur Hälfte. Um die obige Notation zu Nutzen:
    Formel: x = \sqrt{n}
    Genauer gesagt, die Kandidaten k(i) müssen aus der Menge K kommen um n > 3 auf Primalität zu testen:
    Formel: k_i \in K = [2; \lfloor \sqrt {n} \rfloor]

    Beitrag zuletzt geändert: 22.10.2009 20:08:53 von census
  17. census schrieb:
    t-li schrieb:
    sebulon schrieb:

    eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...



    ich bin zwar nicht der fragesteller, aber mich interressiert trotzdem, warum man das machen kann??

    Die Einschränkung ist richig und kann noch verstärkt werden, denn es reicht bis zur Quadratwurzel des Kandidaten zu testen und nicht bis zur Hälfte. Um die obige Notation zu Nutzen:
    Formel: x = \sqrt{n}
    Genauer gesagt, die Kandidaten k(i) müssen aus der Menge K kommen um n &gt; 3 auf Primalität zu testen:
    Formel: k_i \in K = [2; \lfloor \sqrt {n} \rfloor]


    das ist auch richtig, aber die Umsetzung der sqwr - Wurzel-Funktion braucht auch enorm viel leistung... bis 500000 ist vielleicht meine lösung performanter, ab da bis 1000000 kann sich das wieder umkippen... müsste man sich mal die Funktion anschauen...
  18. c****s

    sebulon schrieb: müsste man sich mal die Funktion anschauen...


    FSQRT braucht auf einem Pentium 70 cycles.
    SQRTPS braucht auf einem x86-64 39 cycles.

    Ich hoffe ja mal, dass Pascal das ganze den Proz ausrechnen lässt und nicht zu Fuß per Hand tut.
  19. ja...

    und eine Modulo-Operation? bei google findet man nur rotz...

    aber die braucht doch niemals mehr als 20 cycles?

    und die rechnung würde dann im unteren bereich zwar ein paar mal auftreten... aber im obereb bereich würden sich die ausführungen vermehren...

    man muss ja auch beachten, dass diese ausführung bei JEDER zahl zum einsatz kommt, auch bei zahlen, wo bei der 2 bereits ausgeworfen wird...
  20. c****s

    sebulon schrieb:
    und eine Modulo-Operation? bei google findet man nur rotz...


    Kein Prozessor (zumindest keiner, den ich kenne) kennt eine Modulooperation.
    Alle, die ich kenne, haben eine Operation, die ein Register durch ein anderes teilt und das ganzzahlige Ergebnis in einem Zielregister speichert und den Rest (also den Modulo) in ein anderes.
    Sprich für den Prozessor ist Modulo und Ganzzahldivision dasselbe, weil eine Operation beide Ergebnisse liefert.

    EDIT: typo

    Beitrag zuletzt geändert: 24.10.2009 1:08:28 von census
  21. Autor dieses Themas

    morph01

    morph01 hat kostenlosen Webspace.

    @sebulon: Könntest du mir das ganze vielleicht in asm zusammenbasteln?

    Nein:D Ich kann dem zwar nicht folgen, was du da gelabert hast, werde den pseudocode aber trotzdem einfach mal auf delphi portieren ;) Dankschön :)
  22. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

    lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

Login zum Webhosting ohne Werbung!