The Museum of HP Calculators

HP Articles Forum

[Return to the Index ]
[ Previous | Next ]


HP41 Prime Factorization Revisited

Posted by Ángel Martin on 27 July 2009, 3:58 a.m.

As part of the SandMath Module improvements I decided to enhance the Prime factorization program(s).

I came up with two versions, the first one only uses ALPHA to show the results - similar to previous versions of the program. Using the MCODE function PRIME? speeds up the execution substantially, not that it matters a lot (specially when used an emulated 41 version) but anyway.

But the second (and more interesting) one stores the prime factors (and their exponents) into a Matrix, so that the original number can be rebuilt. Such matrix is dynamically redimensioned as new prime factors are obtained, which adds a little extra execution time - but it's worth it.

With just a few more program steps it also calculates the Euler function of the given number, taking advantage of having all the prime factors conveniently stored in the matrix. Easy when things are properly structured, it'd seem.

Here they are - Version #2 made it into the SandMath module, but you can choose the better one for you :-)

 1 LBL "PRMF"		      1	LBL "PRMF"      1 LBL "EULER"
 2 CF 00		      2	"PRMF"          2 XROM "PRMF"
 3 INT		              3	1,002           3 0
 4 ABS		              4	MATDIM          4 MSIJ
 5 CLA		              5	CLX             5 X<>Y
 6 AIP		              6	MSIJA           6 LBL 07
 7 "@="		              7	RDN             7 MRC+
 8 PRIME?		      8	CF 00           8 1/X
 9 SF 00		      9	INT             9 CHS
10 AIP	     first pf	     10	ABS            10 INCX
11 X=1?		             11	PRIME?         11 *
12 GTO 01		     12	SF 00          12 FC? 09 
13 FS?C 00   we're done	     13	MSR+           13 GTO 07
14 GTO 01	             14	X=1?           14 END 
15 STO 01    save grouping   15	GTO 01
16 ST/ L	             16	FS?C 00
17 LASTX     reduced number  17	GTO 01
18 LBL 05		     18	STO 01
19 E 		             19	ST/ L
20 STO 00    reset counter   20	LASTX
21 RDN		             21	LBL 05
22 LBL 00		     22	E 
23 RCL 01    previous pf     23	STO 00
24 X<>Y		             24	RDN
25 PRIME?		     25	LBL 00
26 SF 00		     26	RCL 01
27 X#Y?	     different PF?   27	X<>Y
28 GTO 02    YES	     28	PRIME?
29 ISG 00    increase count  29	SF 00
30 NOP	     SAME pf         30	X#Y?
31 FS?C 00   was it prime?   31	GTO 02
32 GTO 03    skip if Prime   32	ISG 00
33 ST/ L	  	     33	NOP
34 LASTX     reduced number  34	FS?C 00
35 GTO 00		     35	GTO 03
36 LBL 03    Prime found     36	ST/ L
37 RCL 00		     37	LASTX
38 X=1?		             38	GTO 00
39 GTO 01		     39	LBL 03
40 "@^"		             40	RCL 00
41 AIP		             41	MSR+
42 GTO 01		     42	GTO 01
43 LBL 02    NEW pf	     43	LBL 02
44 STO 01		     44	STO 01
45 RCL 00		     45	RCL 00
46 X=1?		             46	MSR+
47 GTO 03		     47	RDN
48 "@^"		             48	ST/ L
49 AIP		             49	LASTX
50 LBL 03		     50	DIM?
51 RDN		             51	INCX
52 "@*"		             52	MATDIM
53 AIP		             53	X<> Z
54 FS?C 00		     54	MSR+
55 GTO 01		     55	FS?C 00
56 ST/ L		     56	GTO 01
57 LASTX		     57	X<>Y
58 GTO 05		     58	GTO 05
59 LBL 01		     59	LBL 01    
60 AVIEW		     60	E         
61 END		             61	FC? 10    
			     62	MSR+      all done
			     63	STO 00    initiate R00 
			     64	MSIJ      to rebuild the number
			     65	CLA       and display factors
			     66	LBL 06
			     67	MRR+
			     68	AIP
			     69	MRR+
			     70	X=1?
			     71	GTO 04
			     72	"@^"
			     73	AIP
			     74	LBL 04
			     75	Y^X
			     76	ST* 00
			     77	FC? 10
			     78	"@*"
			     79	FC? 10
			     80	GTO 06
			     81	RCL 00
			     82	PROMPT
			     83 END

Edited: 12 Aug 2009, 1:50 a.m.

Password:

[ Return to the Message Index ]

Go back to the main exhibit hall