**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. *