PureBoard

Code: Alles auswählen

Wiki hat geschrieben:
Es ist jedoch kein Verfahren bekannt, das effizient beliebig große Primzahlen generiert, so dass es stets eine größte bekannte Primzahl gab, seitdem sich die Menschen mit Primzahlen befassen. Derzeit ist es 2^32.582.657 - 1, eine Zahl mit 9.808.358 (dezimalen) Stellen, gefunden am 4. September 2006 von einem Professorenteam der Central Missouri State University im Rahmen von George Woltmans GIMPS-Projekt (Great Internet Mersenne Prime Search) zur Suche von Mersenne-Primzahlen. Für den ersten Primzahlbeweis einer Zahl mit mehr als 10 Millionen Dezimalstellen hat die Electronic Frontier Foundation einen Preis von 100.000 US-Dollar ausgeschrieben.

Code: Alles auswählen

For n = 1 To 1000000
    NumberString.s + Str(CryptRandom(10))
  Next

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--);}

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")