Threaded Mode | Linear Mode

fred_76 · (This post was last modified: 04-12-2019 12:44 PM by fred_76.)

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 which one exactly). I don't have them anymore, they were trashed ... sigh ...

I bought a HP32S and that was one of the very best I had. It was stollen during a company convention...

I then asked the company to buy me a calc, it was a HP48S, again it was stollen when my office was broken ! 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 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 a brut force with elimination of 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 trial 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 x=y?            :for 2-3-5-7

P090 GTO P085    :2-3-5-7 are prime 

P091    STOP    :stop to show result X=factor, Y=N

P092    INT/            :press R/S to

P093    GTO P001    :start again to find the next factor

P094    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:10
7 digits       9 999 991             00:00:28
8 digits       99 999 989            00:01:28
9 digits       999 999 937           00:04:36
10 digits      9 999 999 967         00:14:37
11 digits      99 999 999 977        00:46:26
12 digits      999 999 999 989       02:32:18 

All the best

Fred

--- edit : added time for 12 digits
--- edit : added lines P089/P090 to handle exceptions 2/3/5/7