XProfan

Titre de la fenêtre "Statistischer Miller-Rabin Primzahltest"
' (CL) CopyLeft 2018-05 P.Specht, Wien; sans chacun Gewähr!
Windowstyle 24:font 2:set("decimals",17)
Déclarer w$,x!,y!,m!,n!

Repeat

    imprimer "\n Primzahltest [Gruppe = -1]: ";
    input w$ :cas w$="-2":w$="90000103"'encore korrekt
    'Testprime "10,000,007" pas plus erkannt!

    si w$>90000103

        imprimer " *** ZUVERLÄSSIGKEIT sinkt ab 90,000,000 ! ***"
        sound 100,100':continue

    endif

    cas w$="-1":Pause
    n!=val(w$)
    locate %csrlin-1,50:imprimer " MillerRabin_7: ";
    imprimer si(MillerRabin(n!),"PRIMZAHL","NICHT prim.")

Until %clé=27

Cls:set("decimals",0)
declare Anz&,de!,jusqu'à!,le cours!
Von!=90000000'
Bis!=90000500'jusqu'à ca. 90,000,000
cas jusqu'à!>100000000:imprimer "\n longtemps la durée erwarten! \n"
Lauf!=de!+(remodf(de!,2)=0)

REPEAT

    si MillerRabin(le cours!)

        imprimer le cours!,
        inc Anz&

    endif

    le cours!=le cours!+2

UNTIL le cours!>(jusqu'à!+1)

imprimer "\n Anzahl: ",Anz&
'Check: 2871 Primes de 20000 jusqu'à 50000
'Check: 764 Primes de 520000 jusqu'à 530000
'Check: 658 Primes de 5020000 jusqu'à 5030000
'Check: 577 Primes de 50020000 jusqu'à 50030000
beep:sound 2000,200
waitinput
Fin

proc MillerRabin :parameters n!

    cas n!<2:return 0
    cas n!<>intf(n!):return 0
    cas n!<4:return 1
    casenot remodf(n!,2):return 0
    declare s&,d!,x!,res&
    s&=0
    d!=n!-1

    whilenot remodf(d!,2)

        d!=d!/2
        inc s&

    endwhile

    res&=1

    WHILELOOP 7

        x! = modpotf(2+intf(rnd()*(n!-3)),d!,n!)
        Cas (x!=1) OU (x!=n!-1):continue

        whileloop s&-1,1,-1

            x!=remodf(sqr(x!),n!)

            si x!=1:res&=0:Pause:endif

                si x!=n!-1:res&=2:Pause:endif

                endwhile

                cas res&=0:pause

                si res&=2:res&=1:continue:endif

                    cas x!=n!-1:continue
                    res&=0

                ENDWHILE

                return res&

            ENDPROC

            Proc modpotf :parameters x!,y!,m!

                var pot! = 1

                tandis que y!>0

                    si remodf(y!,2)=1

                        pot!=remodf(pot!*x!,m!)
                        y!=y!-1

                    d'autre

                        x!=remodf(sqr(x!),m!)
                        y!=y!/2

                    endif

                endwhile

                return pot!

            endproc

            proc floor :parameters x!

                cas abs(x!)<(10^-35):return 0
                cas x!>0:return intf(x!)
                return (abs(x!-intf(x!)) < 10^-35)-intf(abs(x!-1))

            endproc

            proc remodf :parameters x!,y!

                ' Q: https://de.wikipedia.org/wiki/Modulo , comment dans ADA
                cas abs(x!)<(10^-35):return 0
                cas abs(y!)<(10^-35):return x!
                return ((x!>0)-(x!<0))*abs(x!-y!*floor(x!/y!))

            endproc

            proc frac :parameters x!

                var s!=(x!>0)-(x!<0)
                x!=abs(x!)
                x!=x!-round(x!,0)
                cas x!<0:x!=1+x!
                return s!*x!

            endproc

            proc intf :parameters x!

                var s!=(x!>0)-(x!<0)
                x!=abs(x!)
                x!=x!-frac(x!)
                return s!*x!

            endproc