Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
pzktupel
Anmeldungsdatum: 07.07.2020 Beiträge: 83
|
Verfasst am: 04.09.2021, 11:57 Titel: Primzahltest |
|
|
Hallo, ich bräuchte gerne mal ein kleines Beispielprogramm, wie man in Freebasic zumindest Zahlen <2^64 auf prim testen kann.
Sowas wie isprime(98749817249)...
Welche Biblothek , Befehl usw.
Das wäre echt cool !
Gruß
pzktupel _________________ Umfangreichste Angaben zu Primzahl k-Tupel
https://www.pzktupel.de/ktuplets.php |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4609 Wohnort: ~/
|
Verfasst am: 04.09.2021, 16:38 Titel: |
|
|
Code: | function pruefePrim(z as ulongint) as boolean
for k as ulongint = 2 to sqr(z)
if (z mod k) = 0 then return false
next
return true
end function
open "primzahlen.txt" for output as 1
for z as ulongint = 2 to &hfffffffffffffffe
if pruefePrim(z) then print #1, z & " ist prim."
next
close 1 |
Die Ausführung über den gesamten Zahlenbereich dauert naturgemäß sehr lang (das Testen der Zahl 18446744073709551437 dauerte in meinem Test etwa 30 Sekunden). Wikipedia liefert einen Code zum Sieb des Eratosthenes, der sich die Zwischenergebnisse speichert; wenn sehr oft berechnet werden soll, wäre das wahrscheinlich vorteilhaft.
https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
Wirklich effiziente Algorithmen gibt es da ja nicht, höchstens Plausibilitätstests, die ich jetzt aber spontan nicht im Kopf habe.
Nachtrag: Bei der Schleife beachten, dass sie nicht bis &hffffffffffffffff laufen darf, weil sie sonst "überläuft" und wieder von vorn beginnt. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
pzktupel
Anmeldungsdatum: 07.07.2020 Beiträge: 83
|
Verfasst am: 04.09.2021, 18:08 Titel: |
|
|
Danke für die Zeit.
Aber, sowas meine ich nicht. Triviale Division ist klar und Sieb des Eratosthenes auch.Ich meine eher den Fermattest als Probable-Test. Ich lasse das zwar immer über PFGW laufen, aber für kleine Zahlen ist das zu langsam.
In UBASIC war das zum Bsp. MODPOW(3,N,N)=X
X=3, wahrscheinlich prim...usw.
Es gibt in Freebasic auch solche Codes. _________________ Umfangreichste Angaben zu Primzahl k-Tupel
https://www.pzktupel.de/ktuplets.php |
|
Nach oben |
|
|
St_W
Anmeldungsdatum: 22.07.2007 Beiträge: 949 Wohnort: Austria
|
Verfasst am: 04.09.2021, 18:49 Titel: |
|
|
Eingebaut in der FB-eigenen Laufzeitbibliothek ist meines Wissens nichts dergleichen, d.h. du wirst nicht darum herum kommen eine entsprechende Bibliothek zu verwenden oder den Test in FB zu implementieren.
Auf die Schnelle finde ich da z.B. folgende Beispiele:
https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#FreeBASIC
Da wirds einmal in FB selbst implementiert mit nativen Datentypen, wenn du > 2^64 auch abdecken willst, wirst du um eine Bibliothek wie GMP verwenden wollen, wozu dort auch ein Beispiel ist.
Ich bin leider da zu wenig informiert, aber der Miller-Rabin Test scheint i.A. das beste bekannte Verfahren zu sein (https://arxiv.org/ftp/arxiv/papers/1709/1709.09963.pdf). Für den Spezialfall < 2^64 liest man über optimierte Verfahren (http://ceur-ws.org/Vol-1326/020-Forisek.pdf). Letzteres Paper verweist auf C code, den man bei Bedarf relativ einfach in FB übersetzen könnte (oder als C library compilieren und dann mit FB verwenden könnte) _________________ Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
Nach oben |
|
|
pzktupel
Anmeldungsdatum: 07.07.2020 Beiträge: 83
|
Verfasst am: 04.09.2021, 20:56 Titel: |
|
|
Oha, also gibt es da keine fertigen Befehle.
Das Rad neu zu erfinden macht dann wenig Sinn.
Klar könnte man die duale Zerlegung von N Bestimmen und nacheinander quadrieren , multiplizieren und sehen ob am Ende auch die Basis rauskommt.
Ob das schneller als fertige Tools sind, bezweifel ich dann doch.
Danke ! _________________ Umfangreichste Angaben zu Primzahl k-Tupel
https://www.pzktupel.de/ktuplets.php |
|
Nach oben |
|
|
|