Sorry fürs "Aufwärmen", aber habe gerade wieder Lust und ein wenig Zeit.
Größte bestätigte Primzahl ist z.Z. 2^{57.885.161}-1 und wird als M48 (?) geführt. Das "(?)" rührt daher, das 2^{57.885.161}-1 zwar als Primzahl feststeht, aber möglicherweise auch M49 oder M... sein kann, weil der Zahlenbereich vor 2^{57.885.161}-1 noch nicht sicher komplett auf Primzahlen überprüft wurde (sollte dies falsch sein, Gerd, bitte korrigieren!).
Bleiben wir mal bei M48: Maître Fabrice Bellard (der hat was drauf!) hat sich den Spaß gemacht, die Dezimal-Ausgabe von M48 in einen C-Code von 447-Bytes Länge zu quetschen.
Das sieht dann so aus (ist übrigens von F.Bellard als Freeware freigegeben):
Code: Alles auswählen
int m=1711276033,N=1,t[1<<25]={2},a,*p,i,e=39717691,s,c,U=1;g(d,h){for(i=s;i<1<<
24;i*=2)d=d*1LL*d%m;for(p=t;p<t+N;p+=s)for(i=s,c=1;i;i--)a=p[s]*(h?c:1LL)%m,p[s]
=(m*1U+*p-a)*(h?1LL:c)%m,*p=(a*1U+*p)%m,p++,c=c*1LL*d%m;}main(){while(e/=2){N*=2
;U=U*1LL*(m+1)/2%m;for(s=N;s/=2;)g(40,0);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;
for(s=1;s<N;s*=2)g(983983719,1);for(a=0,p=t;p<t+N;)a+=*p<<(e&1),*p++=a%10,a/=10;
}while(!*--p);for(t[0]--;p>=t;)putchar(48+*p--);}
Ich habe das mal nach PB "übersetzt":
Code: Alles auswählen
;PureBasic 5.31 (x64); Achtung: NUR 64-Bit!
;M48(?): 2^{57.885.161}-1, 17.425.170 Dezimal-Stellen
Global pp.q ;ich bin halt ein Fan von Global...
Global pt.q
Global LL1.q = 1
Global U1.q = 1
Global HV1.q ;Hilfs-Variable
Global m.l = 1711276033
Global N.l = 1
Global a.l
Global i.l
Global e.l = 39717691
Global e1.l
Global s.l
Global c.l
Global U.l = 1
Global HV0.l ;Hilfs-Variable
Global Dez_Stellen.l
Global Dim t.l(1 << 25)
t(0) = 2
pt = @t(0) ;Anfangs-Adresse von Array (t)
Procedure.l g(d, h)
i = s
While i < (1 << 24)
d = (d * LL1 * d) % m
i << 1
Wend
pp = pt ;pp=Zeiger in Array t, pt bleibt Anfangs-Adresse von Array t
While pp < (pt + (N << 2))
i = s
c = 1
While i
If h
a = (PeekL(pp + (s << 2)) * c) % m
Else
a = (PeekL(pp + (s << 2)) * LL1) % m
EndIf
If h
PokeL(pp + (s << 2), (((m * U1) + PeekL(pp) - a) * LL1) % m)
Else
PokeL(pp + (s << 2), (((m * U1) + PeekL(pp) - a) * c) % m)
EndIf
PokeL(pp, ((a * U1) + PeekL(pp))%m)
pp + 4
c = (c * LL1 * d) % m
i - 1
Wend
pp + (s << 2)
Wend
EndProcedure
TA = ElapsedMilliseconds()
e >> 1
While e
N << 1
U = ((U * LL1 * (m + 1)) >> 1) % m
s = N
s >> 1
While s
g(40, 0)
s >> 1
Wend
pp = pt
While pp < (pt + (N << 2))
HV0 = PeekL(pp)
HV1 = HV0 * HV0
PokeL(pp, ((HV1 % m) * U) % m )
pp + 4
Wend
s = 1
While s < N
g(983983719, 1)
s << 1
Wend
a = 0
pp = pt
e1 = e & 1
While pp < (pt + (N << 2))
a + PeekL(pp) << e1
PokeL(pp, (a % 10))
pp + 4
a / 10
Wend
e >> 1
Wend
t(0) - 1
While PeekL(pp) = 0
pp - 4
Wend
OpenFile(0, "M48_PB.txt")
For j = pp To pt Step -4
WriteAsciiCharacter(0, PeekA(j) + 48)
Dez_Stellen + 1
Next
FreeArray(t())
CloseFile(0)
TE = ElapsedMilliseconds() - TA
MessageRequester("Mersenne M48(?) 2^{57.885.161}-1", Str(Dez_Stellen) + " Dezimal-Stellen in " + Str(TE) + "ms")
Auf meinem i7-4790K mit 4.5 GHz dauert es gut 60 Sekunden, dann sind alle 17.425.170 Dezimal-Stellen auf der Platte! In manchen Wohngegenden dauert der Download länger...
Viel Spaß!
Helle
)
