A Faster Algorithm for the Prime Numbers

[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

hacker emblem
Best Viewed With Any Browser Valid HTML 4.01! Valid CSS!

check now

check now