Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
 
FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen  RegistrierenRegistrieren
ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin
Zur Begleitseite des Forums / Chat / Impressum
Aktueller Forenpartner:

Primzahltest

 
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC.
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
pzktupel



Anmeldungsdatum: 07.07.2020
Beiträge: 46

BeitragVerfasst am: 04.09.2021, 11:57    Titel: Primzahltest Antworten mit Zitat

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
_________________
Zum Primzahl k-Tupel Thread
https://matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=232720&start=0
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4398
Wohnort: ~/

BeitragVerfasst am: 04.09.2021, 16:38    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
pzktupel



Anmeldungsdatum: 07.07.2020
Beiträge: 46

BeitragVerfasst am: 04.09.2021, 18:08    Titel: Antworten mit Zitat

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.
_________________
Zum Primzahl k-Tupel Thread
https://matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=232720&start=0
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
St_W



Anmeldungsdatum: 22.07.2007
Beiträge: 943
Wohnort: Austria

BeitragVerfasst am: 04.09.2021, 18:49    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
pzktupel



Anmeldungsdatum: 07.07.2020
Beiträge: 46

BeitragVerfasst am: 04.09.2021, 20:56    Titel: Antworten mit Zitat

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 !
_________________
Zum Primzahl k-Tupel Thread
https://matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=232720&start=0
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC. Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

 Impressum :: Datenschutz