none
C# Primzahl alghorithmus

    Frage

  • Hallo, 

    kennt jemand zufällig einen Algorithmus, welcher prüft,ob eine angegebene Zahl prim ist??

    Dank im Voraus

    Freitag, 9. Mai 2014 17:25

Alle Antworten

  • Hallo,
    schau mal hier:
    http://de.wikibooks.org/wiki/Primzahlen:_Programmbeispiele
    HTH
    Grüße Alexander
    Freitag, 9. Mai 2014 17:28
  • Hi Fragender,

    es gibt leider keinen schnellen Allgorithmus der Prüft ob eine Zahl eine Primzahl ist. Du must sie durch alle Primzahlen die kleiner sind als sie Teilen. (Genauer ca. halb so groß). Wenn sie duch keine ohne Rest teilbar ist. Ist es eine Primzahe, wenn ja ist es keine was auch deine Abbruchbedingung für die Schleife ist.

    Ich denke die Möglichkeit ist sich eine Primzahl Liste zu besorgen, die gibt es netterweise Komma separiert in Internet. So das du sie direkt für ein Array oder eine Liste verwenden kannst. Wenn sie nicht 3mal so groß ist wie deine größte Primzahl, kannst du hingehen über deine Liste zu laufen und schauen ob sie durch eine Zahl Teilbar ist. Am besten bei 2 anfangen ;)

    Wenn sie mehr 3mal so groß ist, gibt es 2 Möglichkeiten.

    1.)Du verwendest auch noch die graden Zahlen (bis zu den Punkt an dem die zu Testende Zahl durch die Primzahl geteilt kleiner ist als die grade Zahl)  , das sollte bis zu dem Quadrat eine Primzahl fuktionieren. 

    2.) Du berechnest die nötigen fehlenden Primzahlen. Das ist recht Rechenaufwändig. Die Zahlen kannst du dann z.B. in einer Datei Speichern und beim nächsten mal wider verwenden.

    Am besten Asynchron Programmieren. ;) 

    Schwer zu Programmieren ist es nicht, die Prüfung kann gegebenen Falls nur lange dauern. Mit einer der gründe wieso Primzahlen bei der Verschlüßelung zu einsatz kommen.

    MFG

    Björn


    • Bearbeitet Palin Freitag, 9. Mai 2014 18:38 Link für 100000 Primzahlen hinzugefügt
    Freitag, 9. Mai 2014 18:37