Das Kefk Network Wiki befindet sich im Testbetrieb.
Fermatscher Primzahltest (Programm-Code)
Aus Kefk.
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:
/* 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);
}
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
gilt.
- tm2 = 1 wenn für ein
gilt.
- tm3 wird jedesmal 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.
