[From PPC Journal V7N1P31-32]
If we have the subset of prime numbers, P = p1, p2, … pn-1, then the integers, n, lying in the interval, pn-1 to pn↑2, that are relatively prime to p1p2…pn-1 are prime. That is, if the integers and p1p2…pn-1 have a G.C.D. of 1 they are prime.
The program below uses John Kennedy's G.C.D. program in V6N5P31. As it is impractical to store all the generated primes, the upper limit, pn↑2, is undefined and it is necessary to take the square root of all the primes passed by the G.C.D. loop to determine pn and thus the upper limit of the interval, pn-1 to pn↑2.
The program ends with a "nonexistent" display when it runs out of registers to store the blocks of p1p2…pn-1 which must be less than 10↑10. However, SIZE 17 will give over 10,000 primes and each additional register will add over 1000
The algorithm has the advantage that it takes little longer to compute the primes in a given numerical interval for the larger primes than for the smaller. For example, the program gives the primes through 1,033 in 10 minutes and the primes through 2,819 in 30 minutes. It takes about 1 hour and 40 minutes for the first 1,000 primes. The printer takes about 15% off these times.
Walter Castles (3152)
STEP | KEY ENTRY | STEP | KEY ENTRY | STEP | KEY ENTRY | ||
---|---|---|---|---|---|---|---|
01 | LBL "PR LIST" | 24 | LBL 02 | 47 | 1 | ||
02 | FIX 0 | 25 | RCL IND 01 | 48 | STO - 01 | ||
03 | CF 29 | 26 | RCL 00 | 49 | 1 E 10 | ||
04 | SF 00 | 27 | LBL 03 | 50 | RCL IND 01 | ||
05 | 1 | 28 | STO Z | 51 | LAST X | ||
06 | STO 03 | 29 | MOD | 52 | * | ||
07 | 2 | 30 | X ≠ 0? | 53 | X > Y? | ||
08 | PSE | 31 | GTO 03 | 54 | GTO 05 | ||
09 | 3.003 | 32 | RDN | 55 | LAST X | ||
10 | STO 02 | 33 | 1 | 56 | ST * IND 01 | ||
11 | PSE | 34 | X ≠ Y? | 57 | GTO 01 | ||
12 | 5 | 35 | GTO 01 | 58 | LBL 05 | ||
13 | STO 00 | 36 | ISG 01 | 59 | 1 | ||
14 | PSE | 37 | GTO 02 | 60 | ST+ 01 | ||
15 | LBL 01 | 38 | RCL 00 | 61 | 1 E - 3 | ||
16 | RCL 02 | 39 | SQRT | 62 | ST+ 02 | ||
17 | STO 01 | 40 | FRC | 63 | LAST X | ||
18 | FC?C 00 | 41 | X = 0? | 64 | STO IND 01 | ||
19 | SF 00 | 42 | GTO 04 | 65 | GTO 01 | ||
20 | 2 | 43 | RCL 00 | 66 | END | ||
21 | FS? 00 | 44 | PSE | ||||
22 | 4 | 45 | GTO 01 | (112 BYTES) | |||
23 | ST+ 00 | 46 | LBL 04 |
Ed. Note: Replacing the PSE instruction sin lines 8,11,14, and 44 with VIEW X instructions and RTN, R/S gave the following table of prime numbers up to 1,000.
[Table omitted]
Last updated October 25, 2006 HTML conversion of article copyright 2006 Eric Smith |
|