Threaded Mode | Linear Mode

Don Shepherd · (This post was last modified: 02-12-2019 01:09 AM by Don Shepherd.)

(02-11-2019 05:16 PM)fred_76 Wrote: Hello

My name is Fred, I am from France. I am used to HP calculators since I was young in the 80's. My father was working in a military-like industry and was supplied with new HP calc every two or three years. Therefore I was always fed with the previous calc he had.

It all started to me with the grey HP65, then the HP67, the HP34, the HP41 (don't remember whiche one exactly). I don't have them anymore, they were trashed ... sight ...

I bought a HP32S and that was one on the very best I had. It was stollen...

I then asked the company to buy me a calc, it was a HP48S, again it was stollen ! The company bought me another calc, a HP48GII that I found desesperatly anoying and hard to program.

My sons just offered me a HP35S and I rediscovered the pleasure of the RPN calculators.

Here is a small code that I find quite effective to determine if a number is prime or not, and that also calculates the factors. It make an extensive use of the stack to avoid unecessary STO/RCLs. It also makes use of fast tricks, such as storing repetitive constants and using included operations. For example [6] [+] is about 4.3 times slower than [RCL+S] (with 6 previously stored in S).

The logic below is to chack all potential factors, eliminating the trivial factors that are multiples of 2, 3 and 5. From 7, you just loop by adding 4,2,4,2,4,6,2,6 to the factor.

Here is the code :

Code:

P001 LBL P :Prime calc routine P002 ENTER :stack N in the pile P003 ENTER :to Z P004 ENTER :so that it is in T at the next line P005 2 P006 STO T :store 2 (t as two) P007 RCL+T :add 2 P008 STO F :store 4 (f as four) P009 RCL+T :add 2 P010 STO S :store 6 (S as six) P011 RCL-F :subtract 4 to get 2 P013 RMDR :check if N is a mult of 2 P013 x=0? :if rest is =0 then N is a mult of 2 P014 GTO P087 :so goto end of calc P015 CLx P016 3 :check if N is a mult of 3 P017 RMDR P018 x=0? P019 GTO P087 P020 CLx P021 LAST x P022 RCL+T :check if N is a mult of 5 P023 RMDR P024 x=0? P025 GTO P087 P026 CLx P027 LAST x P028 RCL+T :check if N is a mult of 7 P029 RMDR P030 x=0? P031 GTO P087 :from that point, it will loop and add successively 4,2,4,2,4,6,2,6 to the :factor and check is N is a mult of the factor P032 CLx P033 LAST X P034 RCL+F :4 P035 RMDR P036 x=0? P037 GTO P087 P038 CLx P039 LAST X P040 RCL+T :2 P041 RMDR P042 x=0? P043 GTO P087 P044 CLx P045 LAST X P046 RCL+F :4 P047 RMDR P048 x=0? P049 GTO P087 P050 CLx P051 LAST X P052 RCL+T :2 P053 RMDR P054 x=0? P055 GTO P087 P056 CLx P057 LAST X P058 RCL+F :4 P059 RMDR P060 x=0? P061 GTO P087 P062 CLx P063 LAST X P064 RCL+S :6 P065 RMDR P066 x=0? P067 GTO P087 P068 CLx P069 LAST X P070 RCL+T :2 P071 RMDR P072 x=0? P073 GTO P087 P074 CLx P075 LAST X P076 RCL+S :6 P077 RMDR P078 x=0? P079 GTO P087 :check if the factor^2 is greater than N, :(SQR is 30% faster than SQRT) :if greater, then N is prime, otherwise loop P080 CLx P081 LAST X P082 x² P083 x<y? P084 GTO P032 P085 Rv :if N is prime P086 RTN :stop and show X=Y=N P087 CLx :if N is not prime P088 LAST X :show first factor P089 STOP :stop to show result X=factor, Y=N P090 INT/ :press R/S to P091 GTO P001 :start again to find the next factor P092 RTN

To use it, just enter the number to test, then press XEQ P.

If the number is prime, X=Y=Number

If the number is not prime, X=first factor found, Y=Number

then press R/S to continue the calc and find the next factors until X=Y

It runs quite fast on my HP35S :

PHP Code:

Digits Prime Number Total Time 6 digits 999 863 00:00:09.53 7 digits 9 999 991 00:00:28.19 8 digits 99 999 989 00:01:27.70 9 digits 999 999 937 00:04:36.35 10 digits 9 999 999 967 00:14:36.59 11 digits 99 999 999 977 00:46:26.18

All the best

Fred

Fred, here is a prime factor finder I wrote for the 12c+, based on work done by Dave Britten. Like yours, it also excludes multiples of 2, 3, and 5 from the trial factor pool.

It determines 999,863 is prime in 2 seconds.
9,999,991 in 5 seconds
99,999,989 in 16 seconds
999,999,937 in 50 seconds

It won't work with your two larger examples.