10REM"
* P R I M A T E *
20REM 8 prime number programs: V.2.
30REM J.Davis - '96.
40MODE7
50VDU23,1,0;0;0;0;
60DIMP%(2000)
70DIMT%(300):DIMU%(300)
80PM$="
* P R I M A T
E * "
90LIN$=CHR$(145)+STRING$(39,",")
100SP$=" Press
SPACE to run
program."
110PG$="
Program "
120P2$="
2 is prime
1"
130Q2$="
2 is prime 1"
140P3$="
3 is prime
2"
150Q3$="
3 is prime 2"
160P5$="
5 is prime
3"
170Q5$="
5 is prime 3"
180PRINTPM$
190PRINT'"
This is a collection of e
ight little
programs about prime number
s. (There
had to be eight of them, so
I could use
the name.) In 8BS-51 Peter
Davy set us"
200PRINT"
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 twea
ked to go"
210PRINT"
faster? Well, yes. Programs
1,3,5 and 6
are concerned with speed usi
ng trial"
220PRINT"
division methods. The maximu
m prime
possible here is 2,147,483,6
47. (Don't
wait up.) Program 8 is usele
ss, but
interesting - it uses Fermat
's Little
Theorem."
230PRINTLIN$;
240PRINT"
Each program has its own i
nfo page,
which appears when the progr
am is
selected from the menu. The
programs
can be called in any order."
250PRINT"
ESCAPE at any time returns
to menu."
260PRINTLIN$;
270PRINTSPC(17);"Press
SPACE for Menu.
";
280G=GET:CLS
290ONERRORVDU23,1,1;0;0;0;:END
300VDU15:PRINTPM$
310PRINT'TAB(14)"
Menu "
320PRINT'"
Program:"
330PRINTCHR$(145)STRING$(8,",")
340PRINT"
1) Skip evens,to sq.root."
350PRINT'"
2) One Liner."
360PRINT'"
3) Skip 3's."
370PRINT'"
4) As 3) + time/gap."
380PRINT'"
5) Composite - fixed diviso
rs."
390PRINT'"
6) Save & use primes."
400PRINT'"
7) Test any number."
410PRINT'"
8) Fermat's Little Theorem.
"
420PRINT'"
ESC To Escape."
430PRINTLIN$;
440G$=GET$
450ONERROR IFERR=17 CLS:VDU23,1,0;0;0;
0;:GOTO290 ELSEPRINT"ERROR at line ";ERL
:END
460IF G$="1" THEN570
470IF G$="2" THEN750
480IF G$="3" THEN870
490IF G$="4" THEN1050
500IF G$="5" THEN1370
510IF G$="6" THEN1890
520IF G$="7" THEN2120
530IF G$="8" THEN2890
540ONERRORVDU23,1,1;0;0;0;:END
550GOTO440
560REM"
570CLS:PRINTPM$
580PRINT'PG$"1 ":PRINT
590PRINT"
This program, in principle
, is the
same as Peter's - it generat
es 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"
600PRINT"
divisors, and it tests only
to the
square root of the number."
610PRINT"
Here the program structure
is simpler
which, with a bit of extra h
elp from
using short (but uninformati
ve) names
for variables, makes the pro
gram run
about five times quicker. It
gets to"
620PRINT"
the 1000th prime (7919 - now
burned
into my subconscious) in 2mi
n 26sec vs.
12min 33sec."
630PRINTLIN$;:PRINTSP$
640G=GET:CLS
650REM"
Program 1
660PRINTP2$:PRINTP3$
670C%=2
680FORA%=5TO2^31-1 STEP2
690S%=SQR(A%)
700FORN%=3TOS% STEP2
710IFA%MODN%<>0 NEXT ELSE N%=S%:NEXT:N
EXT
720C%=C%+1:PRINT"
";A%" is prime
";C%
730NEXT
740REM"
750CLS:PRINTPM$
760PRINT'PG$"2 ":PRINT
770PRINT"
In passing, since Program
1 was so
short, I wondered if it coul
d be
written as a one-liner. It f
ought back,
kicking and screaming, but e
ventually"
780PRINT"
succumbed to a convoluted wa
y of
avoiding an IF statement. Th
e line -
leaving out the first two pr
imes, is:"
790PRINT
800PRINT"CLS:A%=3:C%=2:REPEAT:A%=A%+2:
S%=SQR(A%):FORN%=3TOS%STEP2:N%=N%+(S%-N%
+4ANDA%MODN%=0):NEXT:IFN%<S%+4C%=C%+1:PR
INT"CHR$(34);CHR$(130);CHR$(34)";A%"CHR$
(34);CHR$(133)"is prime"CHR$(129);CHR$(3
4)";C%:UNTIL0 ELSEUNTIL0"
810PRINT'"
This actually runs slower
than the
first program, taking 3min
20sec to
the 1000th prime, vs. 2min
26sec for
Program 1. You can earn bro
wnie points
by writing a quicker one-li
ner."
820PRINTLIN$;:PRINTSP$
830G=GET:CLS
840REM"
Program 2
850CLS:A%=3:C%=2:REPEAT:A%=A%+2:S%=SQR
(A%):FORN%=3TOS%STEP2:N%=N%+(S%-N%+4ANDA
%MODN%=0):NEXT:IFN%<S%+4C%=C%+1:PRINT"
"
;A%"
is prime ";C%:UNTIL0 ELSEUNTIL0
860REM"
870CLS:PRINTPM$
880PRINT'PG$"3 ":PRINT
890PRINT"
Getting more speed from th
is sort of
prime generator means testin
g fewer
numbers and/or using fewer n
umbers to
do each test. It turns out t
hat the"
900PRINT"
only way of adding numbers t
hat gives
a speed boost above just add
ing 2's to
each is adding 4,2,4,2... to
the test
number to skip multiples of
3. Trying
to skip 5's means adding 6,4
,2,4,2,4,6,";
910PRINT"
2, which is slower than tria
l divisions
with 5. Patterns including 7
, 11 etc.
are hopeless. Even adding 4,
2,4,2... to
the divisor slows things dow
n. (See
Programs 5 and 6 for other d
ivisors.)"
920PRINT"
This program just adds the
routine
which skips multiples of 3 i
n the test
number to Program 1. It gets
to the
1000th prime in 2min 6sec vs
. 2m 26s."
930PRINTLIN$;:PRINTSP$
940G=GET:CLS
950REM"
Program 3
960PRINTQ2$:PRINTQ3$:PRINTQ5$
970C%=3:Q%=2
980FORA%=7TO2^31-1 STEP2
990Q%=ABS(Q%-2):A%=A%+Q%:S%=SQR(A%)
1000FORN%=5TOS% STEP2
1010IFA%MODN%<>0 NEXT ELSE N%=S%:NEXT:N
EXT
1020C%=C%+1:PRINT"
";A%" is prime ";C%
1030NEXT
1040REM"
1050CLS:PRINTPM$
1060PRINT'PG$"4 ":PRINT
1070PRINT"
This program is exactly th
e same as
Program 3, but with a couple
of bits
of extra information availab
le. This
is a display of:"
1080PRINT'"
1) Elapsed time (minus disp
lay pause)."
1090PRINT"
2) The largest gap so far be
tween two
consecutive primes, the t
wo primes,
and their position number
s."
1100PRINT'"
This display appears auto
matically
each time there is a new la
rgest gap,
and can be called at any ti
me when the
program is running by press
ing Space."
1110PRINTLIN$;:PRINTSP$
1120G=GET:CLS
1130REM"
Program 4
1140PRINTP2$:PRINTP3$:PRINTP5$
1150C%=3:Q%=2
1160AP%=5:G%=5:FB%=0:TIME=0
1170FORA%=7TO2^31-1 STEP2
1180Q%=ABS(Q%-2):A%=A%+Q%:S%=SQR(A%)
1190FORN%=5TOS% STEP2
1200IFA%MODN%<>0 NEXT ELSE N%=S%:NEXT:N
EXT
1210C%=C%+1:PRINT"
";A%" is prime
";C%
1220IFA%-AP%>G% G%=A%-AP%:LP%=AP%:L%=A%
:CC%=C%:FB%=1:PROCtimegap
1230AP%=A%
1240IFINKEY$(0)=" " PROCtimegap
1250NEXT
1260"
**
1270DEFPROCtimegap
1280T%=TIME/100:PRINT:PRINT"
TIME= ";T%
DIV60"m";T%MOD60"s":PRINT
1290IFC%>217 AND FB%=1 FB%=0:VDU7
1300PRINT"
LARGEST GAP SO FAR: ";G%
1310PRINT"
From PRIME ";LP%" to ";L%
1320PRINT"
At Numbers ";CC%-1" and ";CC
%
1330PRINT
1340FORD=1TO4000:NEXT:TIME=TIME-200
1350ENDPROC
1360REM"
1370CLS:PRINTPM$
1380PRINT'PG$"5 ":PRINT
1390PRINT"
As there is no routine or
pattern for
adding numbers to the diviso
r for more
speed, another approach is n
eeded."
1400PRINT"
As the number being tested
only has
to be divided by primes, wri
ting some
of these into the program in
creases the
speed. In this program, 25 p
rimes,"
1410PRINT"
from 5, are used as initial
divisors.
Logically, these would be st
ored in a
look-up table, but it runs q
uicker if,
thanks to the Copy key, ther
e are 25
consecutive IF statements in
stead."
1420PRINT"
This is a composite progra
m. 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."
1430PRINT"
1000th prime: 1m44s vs. 2m6s
- Prog.3.
5000th prime: 15m4s vs.21m25
s - Prog.3.";
1440PRINTLIN$;:PRINTSP$;
1450G=GET:CLS
1460REM"
Program 5
1470C%=3:Q%=2
1480PRINTQ2$:PRINTQ3$:PRINTQ5$
1490FORA%=7TO3571 STEP2
1500Q%=ABS(Q%-2):A%=A%+Q%:S%=SQR(A%)
1510FORN%=5TOS% STEP2
1520IFA%MODN%<>0 NEXT ELSE N%=S%:NEXT:N
EXT
1530C%=C%+1:PRINT"
";A%" is prime ";C%
1540NEXT
1550Q%=-1:A%=A%-2
1560Q%=Q%*-1:A%=A%+3+Q%
1570IFA%MOD5=0 THEN1560
1580IFA%MOD7=0 THEN1560
1590IFA%MOD11=0 THEN1560
1600IFA%MOD13=0 THEN1560
1610IFA%MOD17=0 THEN1560
1620IFA%MOD19=0 THEN1560
1630IFA%MOD23=0 THEN1560
1640IFA%MOD29=0 THEN1560
1650IFA%MOD31=0 THEN1560
1660IFA%MOD37=0 THEN1560
1670IFA%MOD41=0 THEN1560
1680IFA%MOD43=0 THEN1560
1690IFA%MOD47=0 THEN1560
1700IFA%MOD53=0 THEN1560
1710IFA%MOD59=0 THEN1560
1720IFA%MOD61=0 THEN1560
1730IFA%MOD67=0 THEN1560
1740IFA%MOD71=0 THEN1560
1750IFA%MOD73=0 THEN1560
1760IFA%MOD79=0 THEN1560
1770IFA%MOD83=0 THEN1560
1780IFA%MOD89=0 THEN1560
1790IFA%MOD97=0 THEN1560
1800IFA%MOD101=0 THEN1560
1810IFA%MOD103=0 THEN1560
1820S%=SQR(A%)
1830FORN%=105TOS% STEP2
1840IFA%MODN%=0 N%=S%:F%=1
1850NEXT
1860IF F%=0 C%=C%+1:PRINT"
";A%" is pri
me
";C% ELSE F%=0
1870GOTO1560
1880REM"
1890CLS:PRINTPM$
1900PRINT'PG$"6 ":PRINT
1910PRINT"
This program, in principle
, is the
most efficient of the lot. I
t takes
the idea in Program 5 to its
logical
conclusion by always using o
nly primes
as divisors. It saves the pr
imes it"
1920PRINT"
finds in an array and uses t
hem as
divisors. It's always well a
head of
the game, with more saved at
any time
than it needs."
1930PRINT"
This program is relatively
slow at
first with its extra number
shuffling,
taking 2min 36sec to the 100
0th prime,
but the tortoise beats the h
are on an
overnight run, taking an hou
r less to
the 50,000th prime."
1940PRINTLIN$;:PRINTSP$
1950G=GET:CLS
1960REM"
Program 6
1970PRINTP2$:PRINTP3$:PRINTP5$
1980A%=5:C%=3:F%=0
1990P%(3)=5:Q%=1
2000Q%=Q%*-1:A%=A%+3+Q%
2010S%=SQR(A%):N%=2
2020REPEAT
2030N%=N%+1
2040IFA%MODP%(N%)=0 S%=0:F%=1
2050UNTILP%(N%)>S%
2060IFF%=1 F%=0:GOTO2000
2070C%=C%+1
2080IFC%<2001 P%(C%)=A%
2090PRINT"
";A%" is prime
";C%
2100GOTO2000
2110REM"
2120CLS:PRINTPM$
2130PRINT'PG$"7 (1) ":PRINT
2140PRINT"
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. Th
is usually
takes a few seconds, but can
take up
to a minute."
2150PRINT"
You can enter any number,
odd or
even, but if it is larger th
an the one
above, the program will cras
h."
2160PRINT"
There are three sorts of i
nput you
can use:"
2170PRINT"
1) Enter any number."
2180PRINT"
2) Enter just 'R'.This produ
ces & tests
random numbers up to 2 bi
llion."
2190PRINT"
3) Enter 'R' plus a number,
such as
R654321. This produces an
d tests
random numbers up to the
number."
2200PRINTLIN$;
2210PRINT"
2) & 3) run till stopped wit
h Space."
2220PRINTLIN$;
2230PRINTSPC(15)"Press
SPACE for page 2
.";
2240G=GET:CLS:PRINTPM$
2250PRINT'PG$"7 (2) "
2260PRINT'"
And, if you're a real glu
tton for
punishment, you'll be in ho
g heaven
with the 'All' options. The
se allow
you test consecutive number
s, from any"
2270PRINT"
starting point, almost till
doomsday."
2280PRINT"
4) Enter just 'A'. This prod
uces and
tests all consecutive number
s from 10."
2290PRINT"
5) Enter 'A' plus a number,
which gives
consecutive numbers from tha
t number."
2300PRINT"
Like the random numbers, t
hese run
continuously till stopped wi
th Space."
2310PRINTLIN$;
2320PRINT"
For maximum speed, enter '
X' after
any input, such as A12345678
X.
This cancels the (rather pretty)
running
display of trial divisors. T
his has to"
2330PRINT"
be done after each new input
. You now
get a cursor with large numb
ers, to
show it hasn't gone to sleep
."
2340PRINTLIN$;:PRINTSP$;
2350G=GET:CLS
2360REM"
Program 7
2370PRINTPM$
2380PRINT"
ENTER: Number; R; R+no.; A;
A+no.;
(+X)";
2390PRINTLIN$
2400FR%=0:FA%=0:AL%=10
2410VDU23,1,1;0;0;0;
2420INPUT"
Number to test? "IN$
2430CLS:VDU23,1,0;0;0;0;:PRINTPM$
2440IFRIGHT$(IN$,1)="X" IN$=LEFT$(IN$,L
EN(IN$)-1):D%=1 ELSE D%=0
2450IF LEFT$(IN$,1)<>"A" THEN2510
2460FA%=1
2470IFLEN(IN$)>1 AL%=VAL(RIGHT$(IN$,LEN
(IN$)-1))
2480IFAL%<10 AL%=10
2490ALL%=AL%:AL%=AL%-1
2500GOTO2530
2510IF LEFT$(IN$,1)<>"R" A%=VAL(IN$):GO
TO2610
2520IF LEN(IN$)=1 R%=2000000000 ELSE R%
=VAL(RIGHT$(IN$,LEN(IN$)-1))
2530FR%=1
2540CLS:PRINTPM$
2550PRINT" Press:
SPACE for new run; P/
P
Pause/Go.";
2560PRINTLIN$;
2570IFFA%=1 PRINT"
All numbers from:":P
RINT'" "STR$(ALL%):GOTO2600
2580PRINT"
Random numbers up to:":PRINT
2590PRINT" "STR$(R%)
2600IFFA%=0 A%=RND(R%) ELSE AL%=AL%+1:A
%=AL%
2610IFA%<2 A%=2
2620IFD%=1 ANDA%>10^6 VDU23,1,1;0;0;0;
2630PRINT'"
Number being tested:"
2640PRINT'" "STR$(A%)
2650PRINT'"
Factors: Testing:":PRINT
'SPC(9);
2660M%=3:Z%=0:AA%=A%:F%=0:TIME=0
2670IFA%<4 THEN2760
2680IFA%MOD2=0 A%=A%DIV2:VDU11:PRINT'2;
"
";A%:GOTO2680
2690S%=SQR(A%)
2700VDU11:PRINT
2710FORN%=M%TOS% STEP2
2720IFD%=0 PRINTN%:VDU11
2730IFA%MODN%=0 A%=A%DIVN%:VDU11:PRINT'
N%;"
"A%:Z%=1:M%=N%+2:N%=N%+(S%ANDA%MO
DN%<>0):GOTO2730
2740NEXT
2750IFZ%=1 Z%=0:GOTO2690
2760VDU23,1,0;0;0;0;
2770IFA%=AA% PRINT"
":PRINT'" No Fact
ors:
Time=";INT(TIME/100)+1;"sec. ":P
RINT'" "STR$(A%)"
is a prime number.":PR
INTLIN$;:FORD=1TO5000:NEXT:GOTO2800
2780IFA%>1 AND A%<AA% VDU11:PRINT'A%
2790VDU11:PRINT'CHR$(145)",,,,,,,,,,,"
2800IFFR%=0 GOTO2860
2810FORD=1TO5000:NEXT
2820G$=INKEY$(0)
2830IFG$="P" PRINT'"
PAUSE ":G=GE
T:G$=""
2840IFG$=" " G$="":CLS:GOTO2370
2850GOTO2540
2860PRINT'''"
Press SPACE for new run."
2870G=GET:CLS:GOTO2370
2880REM"
2890CLS:PRINTPM$
2900PRINT'PG$"8 (1) ":PRINT
2910PRINT"
Fermat's Little Theorem sa
ys that,
with P = a prime number and
A
= any number not divisible by P, t
hen:"
2920PRINT"
A^(P-1)MODP=1"
2930PRINT"
For example, taking A as 2
, and
P as 1783 (which is a prime), the
n:"
2940PRINT"
2^1782 MOD1783=1"
2950PRINT'"
Well, there are two probl
ems here.
The first is that a random
scattering
of numbers, for a given A,
will give
1"
2960PRINT"
in the equation, even though
they are
non-primes, so it can't be u
sed to
generate a true list of prim
e numbers."
2970PRINT"
The second problem is that
the number
has to be used as a bloomin'
EXPONENT - my Beeb went belly-up just
at the
thought of it. I tickled its
tummy, and
it revived a bit."
2980PRINTLIN$;
2990PRINTSPC(15)"Press
SPACE for page 2
.";
3000G=GET:CLS
3010PRINTPM$:PRINT'PG$"8 (2) ":PRINT
3020PRINT"
Direct calculation of the
example
above, which would have to b
e done to
complete accuracy, would mea
n working
with numbers about 537 digit
s long."
3030PRINT"
Hmmm... Is there a way aroun
d this?
Mercifully, yes. We don't ac
tually care
what 2^1782 is. What we care
about is
remainders."
3040PRINT"
It turns out that breaking
it up into
tiny bits, multiplying the r
emainders,
breaking that up etc. does t
he trick."
3050PRINT"
This is a dual program.It
uses Fermat
to generate primes and so-ca
lled pseudo
-primes, and checks each wit
h trial
division. The non-primes are
shown."
3060PRINT"
Speed is not a consideration
. The
largest number that can be t
ested is
46,339. You can change base
A
at the start, which gives different
results."
3070PRINTLIN$;:PRINTSP$;
3080G=GET
3090AA%=2
3100CLS:PRINTPM$
3110PRINT'"
As the program runs, the no
n-primes are
displayed automatically. Th
ese are
stored, and a list can be c
alled at any
time by pressing 'N'. The p
rogram then
continues."
3120PRINT"
Pressing Space returns here.
"
3130PRINTLIN$
3140PRINT"
Base A is currently ";AA%
3150PRINT'"
To run with this, just pres
s Return,
or enter a new number."
3160PRINTTAB(0,17);LIN$
3170VDU23,1,1;0;0;0;
3180PRINTTAB(0,15);:INPUT"
Base A ? "Z%
3190IFZ%<>0 AA%=Z%
3200VDU23,1,0;0;0;0;:CLS
3210REM"
Program 8
3220PRINTQ2$:PRINTQ3$
3230REM"
* Fermat Routine *
3240P%=3:C%=2:K%=0
3250P%=P%+2:Q%=P%-1
3260IFP%=46339 THEN3660
3270A%=AA%:X%=1
3280M%=(Q%)MOD2
3290Q%=(Q%)DIV2
3300IFM%=0 THEN3330
3310X%=X%*A%
3320X%=X%MODP%
3330A%=A%^2
3340IFA%>=P% A%=A%MODP%
3350IFQ%=1 THEN3370
3360GOTO3280
3370B%=A%*X%
3380R%=B%MODP%
3390IF R%=1 C%=C%+1:PRINT"
";P%;" is pr
ime
";C%:GOTO3420
3400GOTO3250
3410REM"
* * * *
3420G$=INKEY$(0)
3430IFG$="N" PROCprint
3440IFG$=" " THEN3100
3450S%=SQR(P%)
3460FORN%=3TOS% STEP2
3470IFP%MODN%<>0 THEN3530
3480K%=K%+1
3490T%(K%)=P%:U%(K%)=C%
3500PRINT'"
";P%;" is not a prime. (";K
%;")":PRINT
3510FORD=1TO5000:NEXT
3520N%=S%
3530NEXT
3540GOTO3250
3550"
**
3560DEFPROCprint
3570PRINT
3580IFK%>22 VDU14:PRINT"
Press SHIFT to
scroll.":PRINT
3590FORL%=1TOK%
3600PRINT" ";L%;")
";T%(L%);" (";U%(L%)
;")"
3610NEXT
3620PRINT'"
Press SPACE to continue."
3630G=GET:VDU15:PRINT
3640ENDPROC
3650"
**
3660PRINTLIN$:PRINT"
LIMIT OF PROGRAM."
3670PRINT'"
Press 'N' for list of non-p
rimes.
ESC for menu."
3680G$=GET$:IF G$="N" PROCprint:GOTO367
0 ELSEGOTO3680