10 REM"P R I M A X ? 20 REM Four prime number programs. 30 REM John Davis - '96. 40 MODE7:VDU23,1,0;0;0;0; 50 LIN$=CHR$(145)+STRING$(39,",") 60 PM$=" * P R I M A X ? * " 70 DIMB%(48):DIMT%(300):DIMU%(300) 80 FORN%=1TO48:READA%:B%(N%)=A%:NEXT 90 DATA10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6 100 DATA4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2 110 PRINTPM$ 120 PRINT'" This is another collection of three little programs, following on from PRIMATE in 8BS-52, trying to squeeze outa bit more speed generating prime numbers by trial division." 130 PRINT" Here, the timings to the 1000th primeare: Program 1 -1min11.7sec;Program 2 -1min2.4sec;and,aha!,Program 3 - 55.1sec.One interesting factor that helps the speed is allowing unnecessary"; 140 PRINT"calculations in order to reduce the number of other calculations." 150 PRINT" For structural reasons, these three programs all start at the 7th prime, so, to avoid just printing the first six, they are generated by a separate -but slow - routine." 160 PRINTLIN$; 170 PRINT" ESCAPEat any time gives running timeand Repeat/Menu/Escape options." 180 PRINTLIN$; 190 PRINTSPC(17);"PressSPACEfor Menu."; 200 G=GET:CLS 210 ONERRORVDU23,1,1;0;0;0;:END 220 VDU15:PRINTPM$ 230 PRINT'TAB(14)"Menu " 240 PRINT"Program:" 250 PRINTCHR$(145)STRING$(8,",") 260 PRINT"1)Self-contained one-line routine, skipping multiples of 3 in test numbers and divisors." 270 PRINT" Note that this program can Continue."; 280 PRINT" Time to 1000th prime:1min11.7sec." 290 PRINT'"2)Array skipping multiples of 3, 5, and 7 in test numbers." 300 PRINT" Time to 1000th prime:1min2.4sec." 310 PRINT'"3)Array as2),+ 12 fixed divisors." 320 PRINT" Time to 1000th prime:55.1sec." 330 PRINT'"4)Fermat. This is the same as the Fermat's Little Theorem program in 8BS-52, but tidied up and quicker." 340 PRINT'"ESCTo Escape." 350 PRINTLIN$; 360 G$=GET$ 370 ONERROR IFERR=17 CLS:VDU23,1,0;0;0;0;:GOTO210 ELSEPRINT"ERROR at line ";ERL:END 380 IF G$="1" THEN450 390 IF G$="2" THEN510 400 IF G$="3" THEN560 410 IF G$="4" THEN700 420 ONERRORVDU23,1,1;0;0;0;:END 430 GOTO360 440 REM",,,,,,,,,,,,,,,,,,,,,,, 450 ONERRORT%=TIME:GOTO1260 460 REM"Program 1 470 CLS:F%=1:X%=9:TIME=0 480 PROCfirstsix 490 FORA%=X%TO2^31-1STEP4:Z%=TIME:X%=A%:Y%=C%:S%=SQR(A%+202):FORA%=A%+2TOA%+200STEP2:FORA%=A%TOA%+2STEP2:FORN%=5TOS%STEP6:IFA%MODN%IFA%MOD(N%+2)NEXT:PRINT"";A%;"is prime";C%:C%=C%+1:NEXT:NEXT:NEXTELSEN%=S%:NEXT:NEXT:NEXT:NEXT 500 REM",,,,,,,,,,,,,,,,,,,,,,, 510 ONERRORT%=TIME:GOTO1260 520 REM"Program 2 530 CLS:F%=2:TIME=0:PROCfirstsix 540 A%=1:FORJ%=1TO1STEP0:S%=SQR(A%+210):FORM%=1TO48:A%=A%+B%(M%):FORN%=11TOS%STEP6:IFA%MODN%IFA%MOD(N%+2)NEXT:PRINT"";A%"is prime";C%:C%=C%+1:NEXT:NEXTELSEN%=S%:NEXT:NEXT:NEXT 550 REM",,,,,,,,,,,,,,,,,,,,,,, 560 ONERRORT%=TIME:GOTO1260 570 REM"Program 3 580 CLS:F%=3:TIME=0:PROCfirstsix 590 REM"To 399th prime. 600 A%=1:FORJ%=1TO13:S%=SQR(A%+210):FORM%=1TO48:A%=A%+B%(M%):FORN%=11TOS%STEP6:IFA%MODN%IFA%MOD(N%+2)NEXT:PRINT"";A%"is prime";C%:C%=C%+1:NEXT:NEXTELSEN%=S%:NEXT:NEXT:NEXT 610 REM"From 400th prime. 620 FORJ%=1TO1STEP0:S%=SQR(A%+210):FORM%=1TO48:A%=A%+B%(M%):IFA%MOD11IFA%MOD13IFA%MOD17IFA%MOD19IFA%MOD23IFA%MOD29IFA%MOD31IFA%MOD37IFA%MOD41IFA%MOD43IFA%MOD47IFA%MOD53ELSENEXT:NEXT 630 FORN%=59TOS%STEP6:IFA%MODN%IFA%MOD(N%+2)NEXT:PRINT"";A%"is prime";C%:C%=C%+1:NEXT:NEXTELSEN%=S%:NEXT:NEXT:NEXT 640 REM",,,,,,,,,,,,,,,,,,,,,,, 650 DEFPROCfirstsix 660 A%=1:FORC%=1TO6:FORJ%=1TO1STEP0:A%=A%+1+(1ANDA%>2):S%=SQR(A%):FORN%=3TOS%STEP2:IFA%MODN%ORN%>S%NEXT:PRINT"";A%;"is prime";C%:J%=2:NEXT:NEXTELSEN%=S%:NEXT:NEXT 670 ENDPROC 680 REM",,,,,,,,,,,,,,,,,,,,,,, 690 REM"Program 4 700 AA%=2 710 ONERRORVDU23,1,0;0;0;0;:CLS:GOTO210 720 CLS:PRINT" * F E R M A T * " 730 PRINT'"This program tests all odd numbers, to see which produce '1', including all odd non-primes, using Fermat's Little Theorem. For more info, see 8BS-52." 740 PRINTLIN$; 750 PRINT'"As the program runs, the non-primes aredisplayed automatically. These are stored, and a list can be called at anytime by pressing'N'.The program then continues." 760 PRINT"PressingSpacereturns here." 770 PRINTLIN$ 780 PRINT"BaseAis currently";AA% 790 PRINT'"To run with this, just press Return, or enter a new number." 800 PRINTTAB(0,23);LIN$; 810 VDU23,1,1;0;0;0; 820 PRINTTAB(0,21);:INPUT"BaseA?"Z% 830 IFZ%<>0 AA%=Z% 840 ONERRORT%=TIME:GOTO1260 850 VDU23,1,0;0;0;0;:CLS:F%=4:TIME=0 860 P$="is prime":PRINT"";2P$;1:PRINT"";3P$;2:PRINT"";5P$;3:PRINT"";7P$;4:PRINT"";11P$;5 870 REM"Fermat routine 880 C%=5:K%=0 890 FORP%=11TO46339STEP2 900 Q%=P%-1:A%=AA%:X%=1 910 REPEAT 920 IFQ%MOD2=1X%=(X%*A%)MODP% 930 Q%=Q%DIV2 940 A%=A%*A% 950 IFA%>P%A%=A%MODP% 960 UNTILQ%=1 970 R%=(A%*X%)MODP% 980 IF R%=1 C%=C%+1:PRINT"";P%;"is prime";C%:GOTO1030 990 NEXT 1000 REM"* * * * 1010 GOTO1200 1020 REM"Check 1030 G$=INKEY$(0) 1040 IFG$="N" PROCprint 1050 IFG$=" " THEN710 1060 IFP%MOD3S%=SQR(P%):FORN%=5TOS%STEP6:IFP%MODN%IFP%MOD(N%+2)NEXT:NEXT:GOTO1200ELSEPROCnp:NEXT:NEXT:GOTO1200 1070 "** 1080 DEFPROCnp:K%=K%+1:T%(K%)=P%:U%(K%)=C%:C%=C%-1:PRINT'"";P%;"is not a prime.(";K%;")":PRINT:FORD=1TO3000:NEXT:N%=S%:ENDPROC 1090 "** 1100 DEFPROCprint 1110 PRINT 1120 IFK%>22 VDU14:PRINT"Press SHIFT to scroll.":PRINT 1130 FORL%=1TOK% 1140 PRINT" ";L%;")";T%(L%);"(";U%(L%);")" 1150 NEXT 1160 PRINT'"Press SPACE to continue." 1170 G=GET:VDU15:PRINT 1180 ENDPROC 1190 "** 1200 ONERRORCLS:GOTO210 1210 VDU7:PRINTLIN$:PRINT"LIMIT OF PROGRAM." 1220 PRINT'"PressNfor list of Non-primes. ESCfor menu." 1230 G$=GET$:IF G$="N" PROCprint:GOTO1220ELSEGOTO1230 1240 REM",,,,,,,,,,,,,,,,,,,,,,, 1250 REM"Escape 1260 ONERROR GOTO1390 1270 PRINT'"TIME=";T%DIV6000;"min ";(T%MOD6000)/100;"sec" 1280 PRINT'"Press:Rto Repeat." 1290 IFF%=1PRINTTAB(7)"Cto Continue." 1300 PRINTTAB(7)"Mfor Menu." 1310 PRINTTAB(7)"ESCto Escape." 1320 G$=GET$ 1330 IFG$="R"ONF%GOTO450,510,560,710 1340 IFG$<>"C"ORF%<>1THEN1370 1350 ONERRORT%=TIME:GOTO1260 1360 C%=Y%:TIME=Z%:PRINT:GOTO490 1370 IFG$="M"CLS:GOTO210 1380 GOTO1320 1390 PRINT:VDU23,1,1;0;0;0;