10 REM"* P R I M A T E * 20 REM 8 prime number programs: V.2. 30 REM J.Davis - '96. 40 MODE7 50 VDU23,1,0;0;0;0; 60 DIMP%(2000) 70 DIMT%(300):DIMU%(300) 80 PM$=" * P R I M A T E * " 90 LIN$=CHR$(145)+STRING$(39,",") 100 SP$=" PressSPACEto run program." 110 PG$="Program " 120 P2$="2is prime1" 130 Q2$="2is prime1" 140 P3$="3is prime2" 150 Q3$="3is prime2" 160 P5$="5is prime3" 170 Q5$="5is prime3" 180 PRINTPM$ 190 PRINT'" This is a collection of eight little programs about prime numbers. (There had to be eight of them, so I could usethe name.) In 8BS-51 Peter Davy set us" 200 PRINT"a challenge by a program to generate prime numbers which improved on the speed of the one in 8BS-50. This posed the question: Can it be tweaked to go" 210 PRINT"faster? Well, yes. Programs 1,3,5 and 6are concerned with speed using trial" 220 PRINT"division methods. The maximum prime possible here is 2,147,483,647. (Don't wait up.) Program 8 is useless, but interesting - it uses Fermat's Little Theorem." 230 PRINTLIN$; 240 PRINT" Each program has its own info page, which appears when the program is selected from the menu. The programs can be called in any order." 250 PRINT" ESCAPEat any time returns to menu." 260 PRINTLIN$; 270 PRINTSPC(17);"PressSPACEfor Menu."; 280 G=GET:CLS 290 ONERRORVDU23,1,1;0;0;0;:END 300 VDU15:PRINTPM$ 310 PRINT'TAB(14)"Menu " 320 PRINT'"Program:" 330 PRINTCHR$(145)STRING$(8,",") 340 PRINT"1)Skip evens,to sq.root." 350 PRINT'"2)One Liner." 360 PRINT'"3)Skip 3's." 370 PRINT'"4)As3)+ time/gap." 380 PRINT'"5)Composite - fixed divisors." 390 PRINT'"6)Save & use primes." 400 PRINT'"7)Test any number." 410 PRINT'"8)Fermat's Little Theorem." 420 PRINT'"ESCTo Escape." 430 PRINTLIN$; 440 G$=GET$ 450 ONERROR IFERR=17 CLS:VDU23,1,0;0;0;0;:GOTO290 ELSEPRINT"ERROR at line ";ERL:END 460 IF G$="1" THEN570 470 IF G$="2" THEN750 480 IF G$="3" THEN870 490 IF G$="4" THEN1050 500 IF G$="5" THEN1370 510 IF G$="6" THEN1890 520 IF G$="7" THEN2120 530 IF G$="8" THEN2890 540 ONERRORVDU23,1,1;0;0;0;:END 550 GOTO440 560 REM",,,,,,,,,,,,,,,,,,,,,,, 570 CLS:PRINTPM$ 580 PRINT'PG$"1 ":PRINT 590 PRINT" This program, in principle, is the same as Peter's - it generates a list of primes by trial division, leaving out even numbers as both the number to test to see if it's a prime, and the" 600 PRINT"divisors, and it tests only to the square root of the number." 610 PRINT" Here the program structure is simplerwhich, with a bit of extra help from using short (but uninformative) names for variables, makes the program run about five times quicker. It gets to" 620 PRINT"the 1000th prime (7919 - now burned into my subconscious) in 2min 26sec vs.12min33sec." 630 PRINTLIN$;:PRINTSP$ 640 G=GET:CLS 650 REM"Program 1 660 PRINTP2$:PRINTP3$ 670 C%=2 680 FORA%=5TO2^31-1 STEP2 690 S%=SQR(A%) 700 FORN%=3TOS% STEP2 710 IFA%MODN%<>0 NEXT ELSE N%=S%:NEXT:NEXT 720 C%=C%+1:PRINT"";A%"is prime";C% 730 NEXT 740 REM",,,,,,,,,,,,,,,,,,,,,,, 750 CLS:PRINTPM$ 760 PRINT'PG$"2 ":PRINT 770 PRINT" In passing, since Program 1 was so short, I wondered if it could be written as a one-liner. It fought back,kicking and screaming, but eventually" 780 PRINT"succumbed to a convoluted way of avoiding an IF statement. The line - leaving out the first two primes, is:" 790 PRINT 800 PRINT"CLS:A%=3:C%=2:REPEAT:A%=A%+2:S%=SQR(A%):FORN%=3TOS%STEP2:N%=N%+(S%-N%+4ANDA%MODN%=0):NEXT:IFN%0 NEXT ELSE N%=S%:NEXT:NEXT 1020 C%=C%+1:PRINT"";A%"is prime";C% 1030 NEXT 1040 REM",,,,,,,,,,,,,,,,,,,,,,, 1050 CLS:PRINTPM$ 1060 PRINT'PG$"4 ":PRINT 1070 PRINT" This program is exactly the same as Program 3, but with a couple of bits of extra information available. This is a display of:" 1080 PRINT'"1)Elapsed time (minus display pause)." 1090 PRINT"2)The largest gap so far between two consecutive primes, the two primes, and their position numbers." 1100 PRINT'" This display appears automatically each time there is a new largest gap, and can be called at any time when the program is running by pressing Space." 1110 PRINTLIN$;:PRINTSP$ 1120 G=GET:CLS 1130 REM"Program 4 1140 PRINTP2$:PRINTP3$:PRINTP5$ 1150 C%=3:Q%=2 1160 AP%=5:G%=5:FB%=0:TIME=0 1170 FORA%=7TO2^31-1 STEP2 1180 Q%=ABS(Q%-2):A%=A%+Q%:S%=SQR(A%) 1190 FORN%=5TOS% STEP2 1200 IFA%MODN%<>0 NEXT ELSE N%=S%:NEXT:NEXT 1210 C%=C%+1:PRINT"";A%"is prime";C% 1220 IFA%-AP%>G% G%=A%-AP%:LP%=AP%:L%=A%:CC%=C%:FB%=1:PROCtimegap 1230 AP%=A% 1240 IFINKEY$(0)=" " PROCtimegap 1250 NEXT 1260 "** 1270 DEFPROCtimegap 1280 T%=TIME/100:PRINT:PRINT"TIME=";T%DIV60"m";T%MOD60"s":PRINT 1290 IFC%>217 AND FB%=1 FB%=0:VDU7 1300 PRINT"LARGEST GAP SO FAR:";G% 1310 PRINT"From PRIME";LP%"to";L% 1320 PRINT"At Numbers";CC%-1"and";CC% 1330 PRINT 1340 FORD=1TO4000:NEXT:TIME=TIME-200 1350 ENDPROC 1360 REM",,,,,,,,,,,,,,,,,,,,,,, 1370 CLS:PRINTPM$ 1380 PRINT'PG$"5 ":PRINT 1390 PRINT" As there is no routine or pattern foradding numbers to the divisor for more speed, another approach is needed." 1400 PRINT" As the number being tested only has to be divided by primes, writing some of these into the program increases thespeed. In this program, 25 primes," 1410 PRINT"from 5, are used as initial divisors. Logically, these would be stored in a look-up table, but it runs quicker if, thanks to the Copy key, there are 25 consecutive IF statements instead." 1420 PRINT" This is a composite program. The first 500 (ideally about 400) primes are generated using Program 3. Then the prime divisors take over. Note the speed increase at the 500th prime." 1430 PRINT"1000th prime:1m44s vs. 2m6s - Prog.3. 5000th prime:15m4s vs.21m25s - Prog.3."; 1440 PRINTLIN$;:PRINTSP$; 1450 G=GET:CLS 1460 REM"Program 5 1470 C%=3:Q%=2 1480 PRINTQ2$:PRINTQ3$:PRINTQ5$ 1490 FORA%=7TO3571 STEP2 1500 Q%=ABS(Q%-2):A%=A%+Q%:S%=SQR(A%) 1510 FORN%=5TOS% STEP2 1520 IFA%MODN%<>0 NEXT ELSE N%=S%:NEXT:NEXT 1530 C%=C%+1:PRINT"";A%"is prime";C% 1540 NEXT 1550 Q%=-1:A%=A%-2 1560 Q%=Q%*-1:A%=A%+3+Q% 1570 IFA%MOD5=0 THEN1560 1580 IFA%MOD7=0 THEN1560 1590 IFA%MOD11=0 THEN1560 1600 IFA%MOD13=0 THEN1560 1610 IFA%MOD17=0 THEN1560 1620 IFA%MOD19=0 THEN1560 1630 IFA%MOD23=0 THEN1560 1640 IFA%MOD29=0 THEN1560 1650 IFA%MOD31=0 THEN1560 1660 IFA%MOD37=0 THEN1560 1670 IFA%MOD41=0 THEN1560 1680 IFA%MOD43=0 THEN1560 1690 IFA%MOD47=0 THEN1560 1700 IFA%MOD53=0 THEN1560 1710 IFA%MOD59=0 THEN1560 1720 IFA%MOD61=0 THEN1560 1730 IFA%MOD67=0 THEN1560 1740 IFA%MOD71=0 THEN1560 1750 IFA%MOD73=0 THEN1560 1760 IFA%MOD79=0 THEN1560 1770 IFA%MOD83=0 THEN1560 1780 IFA%MOD89=0 THEN1560 1790 IFA%MOD97=0 THEN1560 1800 IFA%MOD101=0 THEN1560 1810 IFA%MOD103=0 THEN1560 1820 S%=SQR(A%) 1830 FORN%=105TOS% STEP2 1840 IFA%MODN%=0 N%=S%:F%=1 1850 NEXT 1860 IF F%=0 C%=C%+1:PRINT"";A%"is prime";C% ELSE F%=0 1870 GOTO1560 1880 REM",,,,,,,,,,,,,,,,,,,,,,, 1890 CLS:PRINTPM$ 1900 PRINT'PG$"6 ":PRINT 1910 PRINT" This program, in principle, is the most efficient of the lot. It takes the idea in Program 5 to its logical conclusion by always using only primes as divisors. It saves the primes it" 1920 PRINT"finds in an array and uses them as divisors. It's always well ahead of the game, with more saved at any time than it needs." 1930 PRINT" This program is relatively slow at first with its extra number shuffling, taking 2min 36sec to the 1000th prime, but the tortoise beats the hare on an overnight run, taking an hour less to the 50,000th prime." 1940 PRINTLIN$;:PRINTSP$ 1950 G=GET:CLS 1960 REM"Program 6 1970 PRINTP2$:PRINTP3$:PRINTP5$ 1980 A%=5:C%=3:F%=0 1990 P%(3)=5:Q%=1 2000 Q%=Q%*-1:A%=A%+3+Q% 2010 S%=SQR(A%):N%=2 2020 REPEAT 2030 N%=N%+1 2040 IFA%MODP%(N%)=0 S%=0:F%=1 2050 UNTILP%(N%)>S% 2060 IFF%=1 F%=0:GOTO2000 2070 C%=C%+1 2080 IFC%<2001 P%(C%)=A% 2090 PRINT"";A%"is prime";C% 2100 GOTO2000 2110 REM",,,,,,,,,,,,,,,,,,,,,,, 2120 CLS:PRINTPM$ 2130 PRINT'PG$"7 (1) ":PRINT 2140 PRINT" This program allows you to test any number, up to 2,147,483,647 (2^31-1), to see if it is a prime. If it isn't, it will give its factors. This usually takes a few seconds, but can take up to a minute." 2150 PRINT" You can enter any number, odd or even, but if it is larger than the one above, the program will crash." 2160 PRINT" There are three sorts of input you can use:" 2170 PRINT"1)Enter any number." 2180 PRINT"2)Enter just 'R'.This produces & tests random numbers up to 2 billion." 2190 PRINT"3)Enter 'R' plus a number, such as R654321.This produces and tests random numbers up to the number." 2200 PRINTLIN$; 2210 PRINT"2)&3)run till stopped with Space." 2220 PRINTLIN$; 2230 PRINTSPC(15)"PressSPACEfor page 2."; 2240 G=GET:CLS:PRINTPM$ 2250 PRINT'PG$"7 (2) " 2260 PRINT'" And, if you're a real glutton for punishment, you'll be in hog heaven with the 'All' options. These allow you test consecutive numbers, from any" 2270 PRINT"starting point, almost till doomsday." 2280 PRINT"4)Enter just 'A'. This produces and tests all consecutive numbers from 10." 2290 PRINT"5)Enter 'A' plus a number, which givesconsecutive numbers from that number." 2300 PRINT" Like the random numbers, these run continuously till stopped with Space." 2310 PRINTLIN$; 2320 PRINT" For maximum speed, enter 'X' after any input, such asA12345678X.This cancels the (rather pretty) running display of trial divisors. This has to" 2330 PRINT"be done after each new input. You now get a cursor with large numbers, to show it hasn't gone to sleep." 2340 PRINTLIN$;:PRINTSP$; 2350 G=GET:CLS 2360 REM"Program 7 2370 PRINTPM$ 2380 PRINT"ENTER:Number;R; R+no.;A; A+no.;(+X)"; 2390 PRINTLIN$ 2400 FR%=0:FA%=0:AL%=10 2410 VDU23,1,1;0;0;0; 2420 INPUT"Number to test?"IN$ 2430 CLS:VDU23,1,0;0;0;0;:PRINTPM$ 2440 IFRIGHT$(IN$,1)="X" IN$=LEFT$(IN$,LEN(IN$)-1):D%=1 ELSE D%=0 2450 IF LEFT$(IN$,1)<>"A" THEN2510 2460 FA%=1 2470 IFLEN(IN$)>1 AL%=VAL(RIGHT$(IN$,LEN(IN$)-1)) 2480 IFAL%<10 AL%=10 2490 ALL%=AL%:AL%=AL%-1 2500 GOTO2530 2510 IF LEFT$(IN$,1)<>"R" A%=VAL(IN$):GOTO2610 2520 IF LEN(IN$)=1 R%=2000000000 ELSE R%=VAL(RIGHT$(IN$,LEN(IN$)-1)) 2530 FR%=1 2540 CLS:PRINTPM$ 2550 PRINT"Press:SPACEfor new run;P/PPause/Go."; 2560 PRINTLIN$; 2570 IFFA%=1 PRINT"All numbers from:":PRINT'" "STR$(ALL%):GOTO2600 2580 PRINT"Random numbers up to:":PRINT 2590 PRINT" "STR$(R%) 2600 IFFA%=0 A%=RND(R%) ELSE AL%=AL%+1:A%=AL% 2610 IFA%<2 A%=2 2620 IFD%=1 ANDA%>10^6 VDU23,1,1;0;0;0; 2630 PRINT'"Number being tested:" 2640 PRINT'" "STR$(A%) 2650 PRINT'" Factors: Testing:":PRINT'SPC(9); 2660 M%=3:Z%=0:AA%=A%:F%=0:TIME=0 2670 IFA%<4 THEN2760 2680 IFA%MOD2=0 A%=A%DIV2:VDU11:PRINT'2;" ";A%:GOTO2680 2690 S%=SQR(A%) 2700 VDU11:PRINT 2710 FORN%=M%TOS% STEP2 2720 IFD%=0 PRINTN%:VDU11 2730 IFA%MODN%=0 A%=A%DIVN%:VDU11:PRINT'N%;" "A%:Z%=1:M%=N%+2:N%=N%+(S%ANDA%MODN%<>0):GOTO2730 2740 NEXT 2750 IFZ%=1 Z%=0:GOTO2690 2760 VDU23,1,0;0;0;0; 2770 IFA%=AA% PRINT"":PRINT'"No Factors: Time=";INT(TIME/100)+1;"sec. ":PRINT'""STR$(A%)"is a prime number.":PRINTLIN$;:FORD=1TO5000:NEXT:GOTO2800 2780 IFA%>1 AND A%0 AA%=Z% 3200 VDU23,1,0;0;0;0;:CLS 3210 REM"Program 8 3220 PRINTQ2$:PRINTQ3$ 3230 REM"* Fermat Routine * 3240 P%=3:C%=2:K%=0 3250 P%=P%+2:Q%=P%-1 3260 IFP%=46339 THEN3660 3270 A%=AA%:X%=1 3280 M%=(Q%)MOD2 3290 Q%=(Q%)DIV2 3300 IFM%=0 THEN3330 3310 X%=X%*A% 3320 X%=X%MODP% 3330 A%=A%^2 3340 IFA%>=P% A%=A%MODP% 3350 IFQ%=1 THEN3370 3360 GOTO3280 3370 B%=A%*X% 3380 R%=B%MODP% 3390 IF R%=1 C%=C%+1:PRINT"";P%;"is prime";C%:GOTO3420 3400 GOTO3250 3410 REM"* * * * 3420 G$=INKEY$(0) 3430 IFG$="N" PROCprint 3440 IFG$=" " THEN3100 3450 S%=SQR(P%) 3460 FORN%=3TOS% STEP2 3470 IFP%MODN%<>0 THEN3530 3480 K%=K%+1 3490 T%(K%)=P%:U%(K%)=C% 3500 PRINT'"";P%;"is not a prime.(";K%;")":PRINT 3510 FORD=1TO5000:NEXT 3520 N%=S% 3530 NEXT 3540 GOTO3250 3550 "** 3560 DEFPROCprint 3570 PRINT 3580 IFK%>22 VDU14:PRINT"Press SHIFT to scroll.":PRINT 3590 FORL%=1TOK% 3600 PRINT" ";L%;")";T%(L%);"(";U%(L%);")" 3610 NEXT 3620 PRINT'"Press SPACE to continue." 3630 G=GET:VDU15:PRINT 3640 ENDPROC 3650 "** 3660 PRINTLIN$:PRINT"LIMIT OF PROGRAM." 3670 PRINT'"Press'N'for list of non-primes. ESCfor menu." 3680 G$=GET$:IF G$="N" PROCprint:GOTO3670 ELSEGOTO3680