The following warnings occurred:
Warning [2] count(): Parameter must be an array or an object that implements Countable - Line: 795 - File: showthread.php PHP 7.4.33 (FreeBSD)
File Line Function
/showthread.php 795 errorHandler->error





Post Reply 
(29C) Prime numbers up to 10'000
09-02-2018, 11:01 AM (This post was last modified: 09-03-2018 07:45 PM by Thomas Klemm.)
Post: #1
(29C) Prime numbers up to 10'000
Inspired by Jürgen's video printing the Prime numbers up to 10'000 with an HP-19C I took a closer look at its sibling the HP-29C.
It has 30 registers which is enough to store the primes up to 100.
We can use indirect addressing with register 0 so I thought I give it a try.

The first part (lines 01-35) calculates the primes up to 109 and stores them in the registers 3 to 29.

We don't check numbers that are divisible by 2 and 3.
Thus we start with 11, 13, 17, 19, 23, 25,
This is the sequence of numbers congruent to 1 or 5 mod 6: A007310.
The difference of consecutive elements is: 2, 4, 2, 4, 2, 4,
We can calculate that sequence recursively (lines 10-13 and 39-42):

\(\Delta n'=6-\Delta n\)

For numbers smaller than 112 = 121 we only have to check divisibility by 5 and 7.

In the second part (lines 36-60) we continue from 109 with 113, 115, 119, and check only if they are divisible by primes smaller than their square root.

Due to the lack of both the x<y and x≥y instruction we have to use the combination of two comparison instructions:
Code:
49:      14 41 :  x≤y       ; n ≤ π(i)² ?
50:      14 71 :  x=y       ; n = π(i)² ?
51:      13 03 :  GTO 3     ; n ≥ π(i)²

The ISZ command has no upper limit. Thus we have to check that separately (lines 32-34).
In the second part I've omitted that check. The program will stop with an error for the first prime bigger than 1092 = 11,881 which is 11,887.
If you want a decent termination you can add a check after the PAUSE command.

Here's what I came up with:
Code:
01:         05 :  5
02:      23 00 :  STO 0     ; i = 5
03:      23 03 :  STO 3     ; π(3) = 5
04:         02 :  2
05:      23 01 :  STO 1     ; ∆n = 2
06:         07 :  7
07:      23 02 :  STO 2     ; n = 7
08:      23 04 :  STO 4     ; π(4) = 7
09:   15 13 00 :  LBL 0     ; for n loop
10:         06 :  6         ; 6
11:      24 01 :  RCL 1     ; ∆n    6
12:         41 :  -         ; 6-∆n
13:      23 01 :  STO 1     ; ∆n' = 6-∆n
14:   23 51 02 :  STO+ 2    ; n' = n + ∆n
15:      24 02 :  RCL 2     ; n
16:         05 :  5         ; 5     n
17:         71 :  ÷         ; n/5
18:      15 62 :  FRAC      ; {n/5}
19:      15 71 :  x=0       ; 5 | n ?
20:      13 00 :  GTO 0     ; next n
21:      24 02 :  RCL 2     ; n
22:         07 :  7         ; 7     n
23:         71 :  ÷         ; n/7
24:      15 62 :  FRAC      ; {n/7}
25:      15 71 :  x=0       ; 7 | n ?
26:      13 00 :  GTO 0     ; next n
27:      24 02 :  RCL 2     ; n
28:      23 22 :  STO i     ; π(i) = n
29:      14 74 :  PAUSE     ; is prime
30:      15 24 :  ISZ       ; i = i+1
31:      24 00 :  RCL 0     ; i
32:         03 :  3
33:         00 :  0         ; 30    i
34:      14 51 :  x>y       ; 30 > i ?
35:      13 00 :  GTO 0     ; next n
36:   15 13 01 :  LBL 1     ; for n loop
37:         06 :  6         ; 6
38:      24 01 :  RCL 1     ; ∆n    6
39:         41 :  -         ; 6-∆n
40:      23 01 :  STO 1     ; ∆n' = 6-∆n
41:   23 51 02 :  STO+ 2    ; n' = n + ∆n
42:         03 :  3
43:      23 00 :  STO 0     ; i = 3
44:   15 13 02 :  LBL 2     ; for i loop
45:      24 22 :  RCL i     ; π(i)
46:      24 02 :  RCL 2     ; n         π(i)
47:      24 22 :  RCL i     ; π(i)      n     π(i)
48:         71 :  ÷         ; n/π(i)    π(i)
49:      14 41 :  x≤y       ; n ≤ π(i)² ?
50:      14 71 :  x=y       ; n = π(i)² ?
51:      13 03 :  GTO 3     ; n ≥ π(i)²
52:      24 02 :  RCL 2     ; n
53:      14 74 :  PAUSE     ; is prime
54:      13 01 :  GTO 1     ; next n
55:   15 13 03 :  LBL 3     ; n/π(i)
56:      15 62 :  FRAC      ; {n/π(i)}
57:      15 71 :  x=0       ; π(i) | n
58:      13 01 :  GTO 1     ; next n
59:      15 24 :  ISZ       ; i = i+1
60:      13 02 :  GTO 2     ; next i

For those like me that don't have an HP-29C I recommend this online emulator.
You can just copy the listing to the program that pops up when you click the display.

This is the listing of the registers:
Code:
00: i
01: ∆n
02: n
03: 5
04: 7
05: 11
06: 13
07: 17
08: 19
09: 23
10: 29
11: 31
12: 37
13: 41
14: 43
15: 47
16: 53
17: 59
18: 61
19: 67
20: 71
21: 73
22: 79
23: 83
24: 89
25: 97
26: 101
27: 103
28: 107
29: 109

This list of the primes up to 11933 was copied from The First 10,000 Primes:
Code:
      2      3      5      7     11     13     17     19     23     29 
     31     37     41     43     47     53     59     61     67     71 
     73     79     83     89     97    101    103    107    109    113 
    127    131    137    139    149    151    157    163    167    173 
    179    181    191    193    197    199    211    223    227    229 
    233    239    241    251    257    263    269    271    277    281 
    283    293    307    311    313    317    331    337    347    349 
    353    359    367    373    379    383    389    397    401    409 
    419    421    431    433    439    443    449    457    461    463 
    467    479    487    491    499    503    509    521    523    541 
    547    557    563    569    571    577    587    593    599    601 
    607    613    617    619    631    641    643    647    653    659 
    661    673    677    683    691    701    709    719    727    733 
    739    743    751    757    761    769    773    787    797    809 
    811    821    823    827    829    839    853    857    859    863 
    877    881    883    887    907    911    919    929    937    941 
    947    953    967    971    977    983    991    997   1009   1013 
   1019   1021   1031   1033   1039   1049   1051   1061   1063   1069 
   1087   1091   1093   1097   1103   1109   1117   1123   1129   1151 
   1153   1163   1171   1181   1187   1193   1201   1213   1217   1223 
   1229   1231   1237   1249   1259   1277   1279   1283   1289   1291 
   1297   1301   1303   1307   1319   1321   1327   1361   1367   1373 
   1381   1399   1409   1423   1427   1429   1433   1439   1447   1451 
   1453   1459   1471   1481   1483   1487   1489   1493   1499   1511 
   1523   1531   1543   1549   1553   1559   1567   1571   1579   1583 
   1597   1601   1607   1609   1613   1619   1621   1627   1637   1657 
   1663   1667   1669   1693   1697   1699   1709   1721   1723   1733 
   1741   1747   1753   1759   1777   1783   1787   1789   1801   1811 
   1823   1831   1847   1861   1867   1871   1873   1877   1879   1889 
   1901   1907   1913   1931   1933   1949   1951   1973   1979   1987 
   1993   1997   1999   2003   2011   2017   2027   2029   2039   2053 
   2063   2069   2081   2083   2087   2089   2099   2111   2113   2129 
   2131   2137   2141   2143   2153   2161   2179   2203   2207   2213 
   2221   2237   2239   2243   2251   2267   2269   2273   2281   2287 
   2293   2297   2309   2311   2333   2339   2341   2347   2351   2357 
   2371   2377   2381   2383   2389   2393   2399   2411   2417   2423 
   2437   2441   2447   2459   2467   2473   2477   2503   2521   2531 
   2539   2543   2549   2551   2557   2579   2591   2593   2609   2617 
   2621   2633   2647   2657   2659   2663   2671   2677   2683   2687 
   2689   2693   2699   2707   2711   2713   2719   2729   2731   2741 
   2749   2753   2767   2777   2789   2791   2797   2801   2803   2819 
   2833   2837   2843   2851   2857   2861   2879   2887   2897   2903 
   2909   2917   2927   2939   2953   2957   2963   2969   2971   2999 
   3001   3011   3019   3023   3037   3041   3049   3061   3067   3079 
   3083   3089   3109   3119   3121   3137   3163   3167   3169   3181 
   3187   3191   3203   3209   3217   3221   3229   3251   3253   3257 
   3259   3271   3299   3301   3307   3313   3319   3323   3329   3331 
   3343   3347   3359   3361   3371   3373   3389   3391   3407   3413 
   3433   3449   3457   3461   3463   3467   3469   3491   3499   3511 
   3517   3527   3529   3533   3539   3541   3547   3557   3559   3571 
   3581   3583   3593   3607   3613   3617   3623   3631   3637   3643 
   3659   3671   3673   3677   3691   3697   3701   3709   3719   3727 
   3733   3739   3761   3767   3769   3779   3793   3797   3803   3821 
   3823   3833   3847   3851   3853   3863   3877   3881   3889   3907 
   3911   3917   3919   3923   3929   3931   3943   3947   3967   3989 
   4001   4003   4007   4013   4019   4021   4027   4049   4051   4057 
   4073   4079   4091   4093   4099   4111   4127   4129   4133   4139 
   4153   4157   4159   4177   4201   4211   4217   4219   4229   4231 
   4241   4243   4253   4259   4261   4271   4273   4283   4289   4297 
   4327   4337   4339   4349   4357   4363   4373   4391   4397   4409 
   4421   4423   4441   4447   4451   4457   4463   4481   4483   4493 
   4507   4513   4517   4519   4523   4547   4549   4561   4567   4583 
   4591   4597   4603   4621   4637   4639   4643   4649   4651   4657 
   4663   4673   4679   4691   4703   4721   4723   4729   4733   4751 
   4759   4783   4787   4789   4793   4799   4801   4813   4817   4831 
   4861   4871   4877   4889   4903   4909   4919   4931   4933   4937 
   4943   4951   4957   4967   4969   4973   4987   4993   4999   5003 
   5009   5011   5021   5023   5039   5051   5059   5077   5081   5087 
   5099   5101   5107   5113   5119   5147   5153   5167   5171   5179 
   5189   5197   5209   5227   5231   5233   5237   5261   5273   5279 
   5281   5297   5303   5309   5323   5333   5347   5351   5381   5387 
   5393   5399   5407   5413   5417   5419   5431   5437   5441   5443 
   5449   5471   5477   5479   5483   5501   5503   5507   5519   5521 
   5527   5531   5557   5563   5569   5573   5581   5591   5623   5639 
   5641   5647   5651   5653   5657   5659   5669   5683   5689   5693 
   5701   5711   5717   5737   5741   5743   5749   5779   5783   5791 
   5801   5807   5813   5821   5827   5839   5843   5849   5851   5857 
   5861   5867   5869   5879   5881   5897   5903   5923   5927   5939 
   5953   5981   5987   6007   6011   6029   6037   6043   6047   6053 
   6067   6073   6079   6089   6091   6101   6113   6121   6131   6133 
   6143   6151   6163   6173   6197   6199   6203   6211   6217   6221 
   6229   6247   6257   6263   6269   6271   6277   6287   6299   6301 
   6311   6317   6323   6329   6337   6343   6353   6359   6361   6367 
   6373   6379   6389   6397   6421   6427   6449   6451   6469   6473 
   6481   6491   6521   6529   6547   6551   6553   6563   6569   6571 
   6577   6581   6599   6607   6619   6637   6653   6659   6661   6673 
   6679   6689   6691   6701   6703   6709   6719   6733   6737   6761 
   6763   6779   6781   6791   6793   6803   6823   6827   6829   6833 
   6841   6857   6863   6869   6871   6883   6899   6907   6911   6917 
   6947   6949   6959   6961   6967   6971   6977   6983   6991   6997 
   7001   7013   7019   7027   7039   7043   7057   7069   7079   7103 
   7109   7121   7127   7129   7151   7159   7177   7187   7193   7207 
   7211   7213   7219   7229   7237   7243   7247   7253   7283   7297 
   7307   7309   7321   7331   7333   7349   7351   7369   7393   7411 
   7417   7433   7451   7457   7459   7477   7481   7487   7489   7499 
   7507   7517   7523   7529   7537   7541   7547   7549   7559   7561 
   7573   7577   7583   7589   7591   7603   7607   7621   7639   7643 
   7649   7669   7673   7681   7687   7691   7699   7703   7717   7723 
   7727   7741   7753   7757   7759   7789   7793   7817   7823   7829 
   7841   7853   7867   7873   7877   7879   7883   7901   7907   7919 
   7927   7933   7937   7949   7951   7963   7993   8009   8011   8017 
   8039   8053   8059   8069   8081   8087   8089   8093   8101   8111 
   8117   8123   8147   8161   8167   8171   8179   8191   8209   8219 
   8221   8231   8233   8237   8243   8263   8269   8273   8287   8291 
   8293   8297   8311   8317   8329   8353   8363   8369   8377   8387 
   8389   8419   8423   8429   8431   8443   8447   8461   8467   8501 
   8513   8521   8527   8537   8539   8543   8563   8573   8581   8597 
   8599   8609   8623   8627   8629   8641   8647   8663   8669   8677 
   8681   8689   8693   8699   8707   8713   8719   8731   8737   8741 
   8747   8753   8761   8779   8783   8803   8807   8819   8821   8831 
   8837   8839   8849   8861   8863   8867   8887   8893   8923   8929 
   8933   8941   8951   8963   8969   8971   8999   9001   9007   9011 
   9013   9029   9041   9043   9049   9059   9067   9091   9103   9109 
   9127   9133   9137   9151   9157   9161   9173   9181   9187   9199 
   9203   9209   9221   9227   9239   9241   9257   9277   9281   9283 
   9293   9311   9319   9323   9337   9341   9343   9349   9371   9377 
   9391   9397   9403   9413   9419   9421   9431   9433   9437   9439 
   9461   9463   9467   9473   9479   9491   9497   9511   9521   9533 
   9539   9547   9551   9587   9601   9613   9619   9623   9629   9631 
   9643   9649   9661   9677   9679   9689   9697   9719   9721   9733 
   9739   9743   9749   9767   9769   9781   9787   9791   9803   9811 
   9817   9829   9833   9839   9851   9857   9859   9871   9883   9887 
   9901   9907   9923   9929   9931   9941   9949   9967   9973  10007 
  10009  10037  10039  10061  10067  10069  10079  10091  10093  10099 
  10103  10111  10133  10139  10141  10151  10159  10163  10169  10177 
  10181  10193  10211  10223  10243  10247  10253  10259  10267  10271 
  10273  10289  10301  10303  10313  10321  10331  10333  10337  10343 
  10357  10369  10391  10399  10427  10429  10433  10453  10457  10459 
  10463  10477  10487  10499  10501  10513  10529  10531  10559  10567 
  10589  10597  10601  10607  10613  10627  10631  10639  10651  10657 
  10663  10667  10687  10691  10709  10711  10723  10729  10733  10739 
  10753  10771  10781  10789  10799  10831  10837  10847  10853  10859 
  10861  10867  10883  10889  10891  10903  10909  10937  10939  10949 
  10957  10973  10979  10987  10993  11003  11027  11047  11057  11059 
  11069  11071  11083  11087  11093  11113  11117  11119  11131  11149 
  11159  11161  11171  11173  11177  11197  11213  11239  11243  11251 
  11257  11261  11273  11279  11287  11299  11311  11317  11321  11329 
  11351  11353  11369  11383  11393  11399  11411  11423  11437  11443 
  11447  11467  11471  11483  11489  11491  11497  11503  11519  11527 
  11549  11551  11579  11587  11593  11597  11617  11621  11633  11657 
  11677  11681  11689  11699  11701  11717  11719  11731  11743  11777 
  11779  11783  11789  11801  11807  11813  11821  11827  11831  11833 
  11839  11863  11867  11887  11897  11903  11909  11923  11927  11933

The program should run as is on the HP-19C as well. You may want to replace the PAUSE statement with a PRx statement.

Edit: Added comments and stack-diagrams to the code and hopefully some clarifications to the description.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
(29C) Prime numbers up to 10'000 - Thomas Klemm - 09-02-2018 11:01 AM



User(s) browsing this thread: 1 Guest(s)