Finding the largest prime factor on the 15c

The Museum of HP Calculators

HP Forum Archive 21

Finding the largest prime factor on the 15c
Message #1 Posted by Evan Gates on 3 Oct 2012, 12:29 a.m.

I recently had reason to learn how to program my 15c (LE), and had heard that Project Euler is a good way to familiarize oneself with a new programming language/environment. Problems 1 and 2 were trivial, but I had fun with problem 3, finding the largest prime factor of a number. Unfortunately the actual number given is two digits too long for the 15c (600851475143).
To use, key the number to test into the x register then run the program. When the program has finished the largest prime factor will be in the x register. As I'm new to programming the 15c, I'd love any advice, and be interested in more efficient solutions (both speed and size improvements) if anyone is interested.
Listing
001-42,21,11 f LBL A 002- 44 0 STO 0 003- 2 2 Try 2 and 3 first 004- 44 25 STO I 005- 32 1 GSB 1 006- 3 3 007- 44 25 STO I 008- 32 1 GSB 1 009- 5 5 Start on 5 010- 44 25 STO I
011-42,21, 0 f LBL 0 Main loop 012- 32 1 GSB 1 013- 2 2 014-44,40,25 STO + I 015- 32 1 GSB 1 016- 4 4 017-44,40,25 STO + I 018- 22 0 GTO 0
019-42,21, 1 f LBL 1 Check factor in I 020- 45 0 RCL 0 021- 11 SQRT 022- 45 25 RCL I 023-43,30, 7 g TEST 7 Factor in I > square root of what we have left 024- 22 2 GTO 2 So we're done 025- 45 0 RCL 0 026- 34 x<>y 027- 10 / 028- 42 44 f FRAC 029- 43 20 g x=0 Even division 030- 22 3 GTO 3 So do the division and check again 031- 43 32 g RTN Otherwise, on to next factor
032-42,21, 2 f LBL 2 Success, display answer 033- 45 0 RCL 0 034- 31 R/S
035-42,21, 3 f LBL 3 Store remaining number and try factor again 036- 43 36 g LSTx 037- 44 0 STO 0 038- 22 1 GTO 1

Re: Finding the largest prime factor on the 15c
Message #2 Posted by Jim Horn on 3 Oct 2012, 1:25 a.m.,
in response to message #1 by Evan Gates

A few minor suggestions. In "LBL 1", the divisibility test, you take the square root of Register 0. I'd advise taking that square root when you store Register 0, saving that in Register 1. That way, you'll not have to do myriad square roots, a relatively slow operation.
You can also speed the test slightly by using a modulo-30 or modulo-210 test (eliminates divisions by multiples of 5 and 7), just as you do now with modulo-6.
Back in the '70s we beat the dickens out of this subject to get every clock cycle out of this type of code (the HP-67 took 3 hours 45 minutes to discover that 9999999967 was prime). Fascinating that the WP 34S "isprime" returns that same result in under a second!
As I don't have and have never used an HP-15, I can't say much about how to do the divisibility test as fast as possible on same. But there are some tremendous contributors on this forum who will undoubtedly dive in.
Any takers?

Re: Finding the largest prime factor on the 15c
Message #3 Posted by Thomas Klemm on 3 Oct 2012, 11:17 a.m.,
in response to message #1 by Evan Gates

LBL A STO 0 2 GSB 1 3 GSB 1 5 LBL 0 GSB 1 2 RCL + I GSB 1 4 RCL + I GTO 0 LBL 1 STO I RCL 0 RCL / I TEST 8 GTO 2 FRAC TEST 0 RTN RDN LSTx STO 0 RDN GTO 1 LBL 2 RCL 0 R/S
My changes are:

Use the stack to pass parameters to subroutine.
Changed exit-condition: reuse value R.0 / R.I.
Otherwise very nice solution.
Kind regards
Thomas

[ Return to Index | Top of Index ]

Go back to the main exhibit hall