habe heute aus Langeweile mal versucht den Fermat'schen Primzahltest in MATLAB umzusetzen.
Nach Fermat gilt: r^(p-1) mod p = 1 , wenn r und p teilerfremd.
Ich lass MATLAB eine ganze, positive Zahl r (zufällig) generieren, welche zu p teilerfremd ist.
Das prüfe ich, in dem ich sage:
Wenn r=0 oder r=1 oder r mod p = 0 , dann erzeuge eine neue Zahl.
Die Aufgabe besteht also darin, MATLAB folgendes rechnen zu lassen:
Mein Programm funktioniert bis zur Zahl 17, das ist die letzte Primzahl, die erkannt wird.
Vollständiger Programmcode:
Code:
function Fermat_Primzahltest(n) % Fermat'scher Primzahltest % Eine Zahl ist wahrscheinlich Primzahl, wenn gilt a^(n-1) mod n = 1 % dabei gilt: a und n teilerfremd und a Zufallszahl % Funktionsaufruf: Fermat_Primzahltest(n)
% Zu testende Zahl n % n=11; % Pruefen auf n<0,n=0,n=1 if(n==0 || n==1) fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ ') fprintf('\n %d ist keine Primzahl',n) fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ \n\n') return;
elseif(n<0) fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ ') fprintf('\n Bitte nur positive Zahlen verwenden') fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ \n\n') return;
end;
end;
% Zufallszahl von 0 bis 'maxzufall'
maxzufall=10;
% Primzahltest mit 'maxiter' Iterationen und 'zaehler' Durchgaengen
maxiter=1000;
zaehler=1;
for i=1:maxiter
% Zufallszahl r bestimmen, die zu n teilerfremd ist
r=randi(maxzufall,1);
while(r==0 || r==1 || mod(r,n)==0)
r=randi(maxzufall,1);
end;
% Bestimmung von erg
xx=r^(n-1);
if(xx==Inf) fprintf('\n Wert ueberschreitet %d \n',realmax) break;
end;
erg=mod(xx,n);
if(erg~=1) fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ ') fprintf('\n %d ist sicher zusammengesetzt \n Zeuge: %d \n Iterationen: %d',n,r,zaehler) fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ \n\n') break;
end;
zaehler=zaehler+1;
end;
zaehler=zaehler-1;
if(zaehler==maxiter) fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ ') fprintf('\n %d ist wahrscheinlich Primzahl \n Iterationen: %d',n,zaehler) fprintf('\n ++++++++++++++++++++++++++++++++++++++++++++++++++++ \n\n') end;
Ich hasse es wenn die Leute Fragen stellen, man dann versucht sich Mühe zu geben, und diejenigen ihren Thread nie wieder besuchen...
Inception
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 20.04.2013, 11:17
Titel:
Nein, 17 ist keine riesige Zahl
17 ist das letzte korrekte Ergebnis, das MATLAB liefert, danach scheinen die Zahlen in der Berechnung zu groß zu werden, so dass 19 und weitere Primzahlen nicht gefunden werden.
Ich werde deine Links mal ausprobieren (vielen Dank dafür).
Melde mich dann wieder ..
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum 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. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS