The Museum of HP Calculators The Museum of HP Calculators
This program is Copyright © 1976 by Hewlett-Packard and is used here by permission. This program was originally published in the HP-67 Math Pac 2.
This program is supplied without representation or warranty of any kind. Hewlett-Packard Company and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.
| Factors and Primes | |||||
| Shift | Primes | ||||
| Label | n→Fact | From | To | →Primes | Auto? |
| Key | A | B | C | D | E |
This program will find all prime factors of a positive integer n, or list all prime numbers between lower and upper bounds specified by the user.
A routine under LBL a is used in determining the factors of an integer n. This routine selects a trial divisor d and tests d as a factor of n. If d divides n, then n is set to n/d and d is tested as a factor of the new n. If d does not divide n, a new d is selected. The process continues until d > √n at which point n is returned as the final factor. The trial divisor d takes on the values 2,3,5,7; then for d > 10, d takes on those values that satisfy (d-10) mod 30 = 1, 3, 7, 9, 13, 19, 21, or 27. Thus in the first cycle of 30 integers from 11 to 40, d takes on the values 11, 13, 17, 19, 23, 29, 31, and 37. This technique eliminates from the test those values of d (d>10) which are divisible by 2, 3, or 5.
To list primes, a lower bound for the search must be specified. The upper bound is an optional input; if omitted, a default value of 2x109 is assumed. Upper and lower bounds need not be integers. The search for primes also uses LBL a to determine if an integer n has any factors or is indeed prime. Once an integer n (n≥3) has been tested and found to be either prime or non-prime, the next integer tested is n+2.
| Step | Instructions | Input Data/Units | Keys | Output Data/Units |
| 1 | Load side 1 and side 2. | |||
| 2 | To allow automatic output of results, set AUTO mode. | E | 1.00 | |
| 3 | To cancel AUTO mode later. | E | 0.00 | |
| 4 | To find factors, go to step 5; to find primes, go to step 6. | |||
| FACTORS | ||||
| 5 | Key in the integer and find its prime factors (0.00 signals end) | n | A | Factors |
| 0.00 | ||||
| PRIMES | ||||
| 6 | Key in the lower bound of the search for primes. | FROM | B | FROM |
| 7 | (optional) Key in the upper bound of the search (if omitted, TO = 2 x 109). | TO | C | TO |
| 8 | Find all primes between FROM and TO (0.00 signals end of calculation). | D | Primes | |
| 0.00 |
Find the prime factors of 924. Do not set AUTO mode.
Keystrokes Outputs 924 A 2.00 R/S 2.00 R/S 3.00 R/S 7.00 R/S 11.00 R/S 0.00 (end) Thus 924 = 2 x 2 x 3 x 7 x 11.
Find the prime factors of 3623. Do not use AUTO mode.
Keystrokes Outputs 3623 A 3623.00 R/S 0.00 (end) 3623 is prime.
Find all prime numbers between 101 and 125. Use AUTO mode.
Keystrokes Outputs
101 B 125 C E 1.00 (AUTO set)
D 101.00 ***
103.00 ***
107.00 ***
109.00 ***
113.00 ***
0.00 (end)
LINE KEYS 001 *LBL A Factor integer n. 002 STO B 003 ENTER↑ 004 INT 005 X≠Y? If non-integer, halt on Error. 006 GTO 5 007 0 008 STO D Initialize d. 009 X⇔Y 010 X≤Y? If n≤0, halt on Error. 011 GTO 5 012 2 013 EEX 014 9 015 X⇔Y 016 X>Y? 017 GTO 5 If n > 2 x 109, halt on Error. 018 CF 1 F1 clear for factors. 019 GSB a Find factors. 020 RTN 021 *LBL B Lower bound for primes. 022 STO A 023 X<0? If negative, halt on Error. 024 GTO 5 025 ENTER↑ This routine finds smallest 026 INT potential prime ≥ user's 027 X=Y? input. 028 GTO 0 029 1 030 + 031 *LBL 0 032 2 Handle 2 as a special case 033 X⇔Y (only even prime). 034 X=Y? 035 GTO 0 036 2 037 ÷ 038 INT 039 2 040 × 041 1 042 + 043 *LBL 0 044 STO B Store beginning prime L. 045 STO C 046 2 047 EEX 2 x 109 is the default upper bound. 048 9 049 STO E 050 X≤Y? If input ≥ 2 x 109, halt on Error. 051 GTO 5 052 SF 1 Flag 1 set for primes. 053 RCL A 054 RTN 055 *LBL C 056 STO A Upper bound for primes. 057 RCL B 058 - 059 X<0? If upper < lower, halt on Error. 060 GTO 5 061 RCL A 062 INT 063 2 Handle 2 as a special case. 064 X⇔Y 065 X=Y? 066 GTO 0 067 2 068 ÷ This routine finds the greatest potential 069 . prime ≤ user's input. 070 5 071 + 072 INT 073 2 074 × 075 1 076 - 077 *LBL 0 078 STO E 079 RCL A Store final prime U. 080 RTN 081 *LBL D Routine to list primes. 082 0 083 STO D Initialized d←0 084 RCL B 085 2 If L = 2, print 2, add 1 and go. 086 X⇔Y 087 X=Y? 088 GTO 0 089 1 If L = 1, print 1, 2, add 1 and go. 090 X≠Y? 091 GTO 1 092 GSB e If L ≠ 1 and L ≠ 2, go directly to LBL 1 093 + 094 RCL E 095 X⇔Y 096 X>Y? 097 GTO 4 098 *LBL 0 099 GSB e 100 1 Output 2 101 GTO 8 102 *LBL 1 103 GSB a 104 RCL B Begin main loop. 105 RCL C Check for factors of current n (RB). 106 X=Y? if RB = RC, n is prime. 107 GSB e Output n. 108 2 109 *LBL 8 110 + 111 STO C Set n to next potential prime. 112 STO B 113 RCL E 114 X⇔Y 115 X>Y? If n > U, exit. 116 GTO 4 117 0 118 STO D Else loop again. 119 GTO 1 120 *LBL a Subroutine called from both A & D which 121 2 finds factors of n. 122 GSB 3 123 X=0? 124 RTN 125 1 Check first if n is divisible by 2, 3, 5, 126 GSB 3 or 7 127 X=0? LBL 2 check for division by integers 128 RTN whose position in a cycle of 30 corresponds 129 2 to 11, 13, 17, 19, 23, 29, 31, or 37 130 GSB 3 131 X=0? 132 RTN 133 2 134 GSB 3 135 X=0? 136 RTN 137 *LBL 2 138 4 139 GSB 3 11 (=7+4) 140 X=0? 141 RTN 142 2 143 GSB 3 13 (=11+2) 144 X=0? 145 RTN 146 4 147 GSB 3 17 (=13+4) 148 X=0? 149 RTN 150 2 151 GSB 3 19 (=17+4) 152 X=0? 153 RTN 154 4 155 GSB 3 23 (=19+4) 156 X=0? 157 RTN 158 6 159 GSB 3 29 (=23+6) 160 X=0? 161 RTN 162 2 163 GSB 3 31 (=29+2) 164 X=0? 165 RTN 166 6 167 GSB 3 37 (=31+6) 168 X=0? 169 RTN Loop again for next 30. 170 GTO 2 171 *LBL 3 172 RCL D Test if d|n 173 + 174 STO D d← d + x 175 RCL B n 176 X⇔Y 177 ÷ n/d 178 LST X d, n/d 179 X>Y? If d > n/d, then d > √n 180 GTO 0 Exit. 181 X⇔Y 182 INT [n/d] ::= INT(n/d) 183 LST X n/d, [n/d] 184 X≠Y? if non-integer, d does not 185 RTN divide n. 186 STO B Else n← n/d 187 F1? 188 CLX If finding primes, exit. 189 F1? 190 RTN 191 RCL D If factoring, output d. 192 GSB e 193 0 Check for d a multiple factor. 194 GTO 3 195 *LBL 0 Coming here means n is prime. 196 F1? If finding primes, exit. 197 CLX 198 F1? 199 RTN Else output last n. 200 RCL B 201 GSB e 202 *LBL 4 203 CLX Exit displaying 0. 204 F0? 205 PRT SPC 206 RTN 207 *LBL E 208 F0? Auto toggle. 209 GTO 0 210 SF 0 211 1 212 RTN 213 *LBL 0 214 CF 0 215 0 216 RTN 217 *LBL e Output routine. 218 F0? Print if AUTO. 219 PRTX 220 F0? 221 RTN 222 R/S Halt if not. 223 RTN
A Used B n C Potential prime D d E U
Go back to the software library
Go back to the main exhibit hall