Diskussion:Fermatscher Primzahltest (Programm-Code) - Versionsgeschichte

Fmrauch: /* Init-Quelle */ das gehört nicht in die Diskussion

2025-08-17T19:49:08Z

Init-Quelle: das gehört nicht in die Diskussion

← Nächstältere Version		Version vom 17. August 2025, 19:49 Uhr
Zeile 120:		Zeile 120:

	Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.		Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.

	~~== Init-Quelle ==~~
	~~Entnommen aus der:~~
	~~[http://de.wikipedia.org/wiki/Fermatscher_Primzahltest_(Programm-Code) Wikipedia]~~

	~~Autoren: Riemanns Freund , YMS , Andreas aus Hamburg in Berlin, Revolus, Nuuk, Kubieziel, Bananeweizen, P. Birken, Srbauer, Arbol01, Markus Schweiß~~

	~~{{Link_LD_fehlt}}~~

	--[[Benutzer:Arbol01\|Arbol01]] 14:08, 13. Dez. 2009 (UTC)		--[[Benutzer:Arbol01\|Arbol01]] 14:08, 13. Dez. 2009 (UTC)

Fmrauch: das ist hier die Diskussionsseite

2025-08-17T19:44:00Z

das ist hier die Diskussionsseite

← Nächstältere Version		Version vom 17. August 2025, 19:44 Uhr
Zeile 120:		Zeile 120:

	Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.		Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.

	~~[[Kategorie:Primzahl]]~~
	~~[[Kategorie:Programmierung]]~~

	== Init-Quelle ==		== Init-Quelle ==

Fmrauch: das hat hier nichts zu suchen

2025-08-17T19:43:31Z

das hat hier nichts zu suchen

← Nächstältere Version		Version vom 17. August 2025, 19:43 Uhr
Zeile 131:		Zeile 131:

	{{Link_LD_fehlt}}		{{Link_LD_fehlt}}
	~~[[Kategorie:WikiPedia Deleted]]~~

	--[[Benutzer:Arbol01\|Arbol01]] 14:08, 13. Dez. 2009 (UTC)		--[[Benutzer:Arbol01\|Arbol01]] 14:08, 13. Dez. 2009 (UTC)

Whorf am 18. August 2019 um 09:54 Uhr

2019-08-18T09:54:11Z

← Nächstältere Version		Version vom 18. August 2019, 09:54 Uhr
Zeile 121:		Zeile 121:
	Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.		Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.

	[[Kategorie:~~Zahlentheorie~~]]		[[Kategorie:Primzahl]]
			[[Kategorie:Programmierung]]

	== Init-Quelle ==		== Init-Quelle ==

Arbol01 am 13. Dezember 2009 um 14:19 Uhr

2009-12-13T14:19:16Z

← Nächstältere Version		Version vom 13. Dezember 2009, 14:19 Uhr
Zeile 1:		Zeile 1:
			Der Artikel wurde in der Wikipedia nicht in dem Sinne gelöscht, sondern der Quellcode nur in den Artikel ''Fermatscher Primzahltest'' verschoben.

			== Quellcode ersetzt ==

	Hier das Programm, das vorher in dem Artikel stand:		Hier das Programm, das vorher in dem Artikel stand:

Arbol01: Die Seite wurde neu angelegt: „Hier das Programm, das vorher in dem Artikel stand: '''Fermatscher Primzahltest (Programm-Code)''' ist ein aus Fermatscher Primzahltest ausgelagerter Quellco...“

2009-12-13T14:08:34Z

Die Seite wurde neu angelegt: „Hier das Programm, das vorher in dem Artikel stand: '''Fermatscher Primzahltest (Programm-Code)''' ist ein aus Fermatscher Primzahltest ausgelagerter Quellco...“

Neue Seite

Hier das Programm, das vorher in dem Artikel stand:

'''Fermatscher Primzahltest (Programm-Code)''' ist ein aus [[Fermatscher Primzahltest]] ausgelagerter Quellcode.

Hier ein Programm dazu:
C-Quellcode für ein Programm, das nach dem kleinen Fermatschen Satz, Primzahlen, Pseudoprimzahlen und Carmichaelzahlen unterscheidet:
<source lang=cpp>
/* Ein Programm, zur Ermittlung von Primzahlen, Pseudoprimzahlen */
/* und Charmichaelzahlen (starke Pseudoprimzahlen) */
/* Ein extrem langsames Programm */

#include <stdio.h>

int primfeld[400000];
int tst[400000];

unsigned long modup(unsigned long x, unsigned long y)
{
unsigned long mindex, xtemp = 1;
for(mindex=1;mindex<=(y-1);mindex++)
{
xtemp *= x;
xtemp %=y;
}
return(xtemp);
}

void main()
{
unsigned long index, index2, anzp=1, m, dtm;
int tm1, tm2, tm3, gtm;
FILE *prim;
FILE *pspr;
FILE *cnbr;
prim = fopen("prim.dat","w");
pspr = fopen("pspr.dat","w");
cnbr = fopen("cnbr.dat","w");
primfeld[1] = 2;
for(index=3;index<=4000000;index++)
{
tm1 = 0;
tm2 = 0;
tm3 = 0;
/* faktor$ = "" */
for(index2=1;index2<=anzp;index2++)
{
m = modup(primfeld[index2], index);
tst[index2] = m;
if (m == 1)
{
tm1 = 1;
tm3++;
}
if ( m != 1) { tm2 = 2; }
}
gtm = tm1 + tm2;
if (gtm == 1)
{
anzp++;
primfeld[anzp] = index;
fprintf(prim,"%d \n",index);
}
if (gtm == 3)
{
dtm=anzp/2;
if (tm3 < dtm)
{
fprintf(pspr,"%d: ",index);
for(index2=1;index2<=anzp;index2++)
{
m = modup(primfeld[index2], index);
if (m == 1)
{
fprintf(pspr,"%d, ",primfeld[index2]);
}
}
fprintf(pspr,"\n",0);
}
if (tm3 >= dtm)
{
fprintf(pspr,"%d: ",index);
for(index2=1;index2<=anzp;index2++)
{
m = modup(primfeld[index2], index);
if (m != 1)
{
fprintf(cnbr,"N%d, ",primfeld[index2]);
}
}
fprintf(cnbr,"\n",0);
}
}
}
fclose(prim);
fclose(pspr);
fclose(cnbr);
}
</source>

== Erläuterungen zum Programm ==

Da das Programm nicht nur eine Zahl auf ihre Primalität prüft, sondern alle Zahlen von 3 bis Obergrenze abtestet, wird ein Array namens Primfeld bereitgehalten, in dem alle Primzahlen, die so nach und nach gefunden werden, abgelegt werden. Die 2 wird als Primzahl vorgegeben.

Getestet werden die Primzahlkandidaten nur durch die Primzahlen in dem Array.

Die Variablen tm1, tm2, tm3, gtm sind Prüfvariablen:

:tm1 = 1 wenn für ein <math>a^{n-1} \mod a = 1</math> gilt.
:tm2 = 1 wenn für ein <math>a^{n-1} \mod a <> 1</math> gilt.
:tm3 wird jedes Mal um 1 erhöht, wenn die Bedingung für tm1 erfüllt wird.
:gtm = tm1 + tm2, woraus folgt:
::Wenn gtm = 1 ist, dann ist die zu prüfende Zahl n eine Primzahl
::Wenn gtm = 2 ist, dann ist die zu prüfende Zahl n eine ganz gewöhnliche Zahl
::Wenn gtm = 3 ist, dann ist die zu prüfende Zahl n eine Pseudoprimzahl
::Wenn gtm = 3 ist, und es gilt, dass die Anzahl der gefundenen Pseudoprimbasen größer oder gleich der Hälfte der testenden Primzahlen ist, dann ist die zu prüfende Zahl n eine Carmichael-Zahl.

Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.

[[Kategorie:Zahlentheorie]]

== Init-Quelle ==
Entnommen aus der:
[http://de.wikipedia.org/wiki/Fermatscher_Primzahltest_(Programm-Code) Wikipedia]

Autoren: Riemanns Freund , YMS , Andreas aus Hamburg in Berlin, Revolus, Nuuk, Kubieziel, Bananeweizen, P. Birken, Srbauer, Arbol01, Markus Schweiß

{{Link_LD_fehlt}}
[[Kategorie:WikiPedia Deleted]]

--[[Benutzer:Arbol01|Arbol01]] 14:08, 13. Dez. 2009 (UTC)