(35s) Primality test using optimized brut force
02-14-2019, 01:44 PM (This post was last modified: 02-14-2019 01:52 PM by fred_76.)
Post: #1
 fred_76 Junior Member Posts: 33 Joined: Feb 2019
(35s) Primality test using optimized brut force
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