'Subject: Find the next probable prime >= N with the Miller-Rabin test.
'Author : Sjoerd.J.Schaper
'Date   : 13-01-2004
'Code   : QuickBasic, PDS, VBdos
REM $LANG: "qb"
REM $INCLUDE: 'largeint.bi'
CONST N = 0, m = 1, w = 7 '           number of witnesses
d = LargeInit(m, "nxtprime")
CLS : tim# = TIMER: lin = 7

begin:
LOCATE 1, 1
PRINT "   +----------------------------------------+"
PRINT "   |  input N to find the next prime >= N,  |"
PRINT "   |  0 to exit.                            |"
PRINT "   |                                        |"
PRINT "   +----------------------------------------+"
LOCATE 4, 7: INPUT ; "N"; iN$
IF INSTR(iN$, "'") THEN GOTO begin
IF VAL(iN$) < 1 THEN GOTO eind

LOCATE lin, 1
Readst N, iN$
Printn N, " N = ", "", 2
IF Isf(N, 1) THEN
   Letf N, 2: GOTO jump
ELSE
   IF Isf(N, 2) OR Isf(N, 3) THEN GOTO jump
END IF

Dup N, m: d = 5: df = 4
r = Divint(m, 6)
IF r < 2 THEN d = 1: df = 2
Inc N, d - r

Dup N, m: d = Divint(m, MD) '         N mod 10000
PRINT " searching...";
lin = CSRLIN
DO
   IF (df AND 3) = 0 THEN
      LOCATE lin, 14: PRINT d;
   END IF
   IF IsPPrm(N, m, w) THEN EXIT DO
   df = 6 - df: d = d + df
   Inc N, df
LOOP
LOCATE lin, 1

jump:
Printn N, " P = ", "", 2
Prints "", 1: lin = CSRLIN
GOTO begin

eind:
LOCATE lin, 1
g$ = STR$(CSNG(TIMER - tim#))
Prints "Timer:" + g$ + " s", 1
CALL Term
SYSTEM

