HP Forums
(35s) Primality test using optimized brut force - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (35s) Primality test using optimized brut force (/thread-12425.html)

(35s) Primality test using optimized brut force - fred_76 - 02-14-2019 01:44 PM

A program to find the factors of a number, or check if it is prime.

Enter N then press XEQ P

Returns
  • X=Y=N if N is prime
  • Y=factor Y=N if N is a multiple of X,
    then press R/S to continue the calculation with N/X

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    R↓       :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

For those who still care :
LBL P
LN=314
CK=91DA

Running time
6 digits (999 983) = 00:00:09.7
7 digits (9 999 991) = 00:00:28.2
8 digits (99 999 989) = 00:01:27.7
9 digits (999 999 937) = 00:04:36.4
10 digits (9 999 999 967) = 00:14:37.0
11 digits (99 999 999 977) = 00:46:26.2
12 digits (999 999 999 989) = 02:32:18.3

Discussion thread is here : http://www.hpmuseum.org/forum/thread-12406-post-112029.html#pid112029

Feel free to comment in the discussion thread !

Fred