Examining Prime Numbers: Two Programs

The prime numbers are a set of numbers which have as their distinguishing property the fact that they are divisible evenly only by themselves and one. Thus, 2, 3, 5, and 7 are primes, whereas 4, 6, and 9 are not. While 1 would seem to fit the definition, it is not usually considered to be a prime.

Aside from their own interesting property, mathematics teachers introduce prime numbers in the middle grades because they add a bit of puzzle-like fun to the class and because they provide an excellent vehicle for an introduction to factoring. They make an interesting subject for computers both because the testing of a number to see if it is a prime is an excellent application of the computer’s ability to perform many calculations rapidly and because they provide a good illustration of the use to which “IF…THEN” and “FOR…NEXT” statements can be put.

The first of the two programs below tests a set of numbers to see which members of the set are primes. The program asks for (and enters with INPUT statements) the beginning and the end of the set, and displays those numbers in the chosen set which are primes. For example, if in response to the opening statement:

ENTER STARTING NUMBER,

you enter 20, and, if in response to the next statement:

ENTER ENDING NUMBER,

you enter 30, the result:

THE PRIMES BETWEEN 20 AND 30
ARE:
23, 29

will be displayed.

The second program produces the prime factorization of a selected number. The prime factorization of a number is the set of prime numbers which, when multiplied together, produce the number as their product. For example, the prime factors of 72 are 2, 2, 2, 3, and 3, since 2 X 2 X 2 X 3 X 3 = 72. If, in response to the opening statement:

ENTER A NUMBER BETWEEN 2 AND
32,767

you enter 72, the computer will display:

THE PRIME FACTORS OF 72 ARE:
2, 2, 2, 3, 3,

If a prime number is selected for factorization, the computer will display this fact. If, for example, you entered the number 73, the computer will display:

73 IS A PRIME, AND HAS NO PRIME
FACTORS EXCEPT ITSELF.

In addition to producing their answers, both programs cycle again upon entering the number 1. The entering of any number other than 1 will stop the program.

Both programs are written for the 4K ROM. Both can be entered together and will run on 1K RAM, although, if both programs are in the computer, you can run out of memory if you choose a particularly wide range of values when running the first. To run the first program simply use the RUN command; to run the second program, you must enter RUN 1010. When running these programs for the first time it is a good idea to use a short range of values for the first or a low number for the second. Wide ranges or high values can take some time to run. Once you are sure the programs are running well, save them on tape, delete the second. If you plan to take a break, try a wide range (say M = 1, N = 500 or 1000). This will take many minutes to run!

Testing a Range of Numbers for Primes

 10 CLS
 20 PRINT                                   20, 30 lower the display.
 30 PRINT
 40 PRINT "ENTER STARTING NUMBER"
 50 INPUT M                                 50 accepts the starting number
 60 CLS                                     of the set to be tested.
 70 PRINT                                   70, 80 lower the display.
 80 PRINT
 90 PRINT "ENTER ENDING NUMBER"
100 INPUT N                                 100 accepts the ending number of
110 CLS                                     the set to be tested.
120 PRINT                                   120, 130 lower the display.
130 PRINT
140 PRINT "THE PRIMES BETWEEN#";M;"#AND#";N
150 PRINT "ARE:#"
160 PRINT
170 IF M=2 THEN PRINT "2,#";                170 insures that 2 will be displayed.
180 FOR J=M TO N                            180 presents each number in turn.
190 FOR K=2 TO J-1                          190, 200 test each possible divisor;
200 LET Q=J/K                               if a divisor is found, 210 drops
210 IF J=Q*K THEN GO TO 240                 the number from further consideration.
220 NEXT K
230 PRINT J;",#";                           230 prints only those numbers found
240 NEXT J                                  not to have a divisor.
250 PRINT
260 PRINT
270 PRINT "TO TEST NEW NUMBERS, ENTER 1"    270 to 290 repeat the program
280 INPUT Z
290 IF Z=1 THEN GO TO 10
300 STOP

Note: If the 8K ROM is used, line 210 must be replaced by something like:

210 IF J=INT(Q)*K THEN GO TO 240

Prime Factorization

1010 CLS
1020 PRINT                          Lowers display for neatness.
1030 PRINT
1040 PRINT "ENTER A NUMBER BETWEEN  Asks for number to be factored.
     2 AND 32,767"
1050 INPUT N                        Enters number to be factored.
1060 CLS
1070 PRINT                          Lowers display.
1080 PRINT
1090 IF N=2 THEN GO TO 1180         Identifies 2 as a prime number.
1100 PRINT "THE PRIME FACTORS OF#";
     N;"#ARE:#"
1110 FOR J=2 TO N/2                 Tests possible divisors.
1120 LET Q=N/J                      Defines the quotient.
1130 IF N-Q*J=0 THEN GO SUB 1210    Identifies a divisor which has no remainder.
1140 NEXT J                         Goes to next divisor.
1150 CLS
1160 PRINT                          Lowers display.
1170 PRINT
1180 PRINT N;"#IS A PRIME, AND      Displays and identifies a number
     HAS NO PRIME FACTORS           if it is a prime
     EXCEPT ITSELF"
1190 PRINT
1200 GO TO 1280
1210 PRINT J;",#";                  Begin subroutine; prints prime factor.
1220 IF Q=1 THEN GO TO 1260         Determines if all factors have been found.
1230 LET N=Q                        Factors out the divisor.
1240 LET J=J-1                      Resets J to try the same factor.
1250 RETURN
1260 PRINT
1270 PRINT
1280 PRINT "TO TEST A NEW NUMBER, ENTER 1   Presents option to rerun program.
1290 INPUT A
1300 IF A=1 THEN GO TO 1010
1310 STOP

Note: To run the program with 8K ROM, line 1130 must be changed to something like:

1130 IF INT(Q)=Q THEN GO SUB 1210