(49G) Prime Counting Programme

[Gerald H]

For integer input the programme returns the number of prime numbers up to & including the input.

eg For input

5

the programme returns

3.

Maximum input is 1680, higher values produce an error.

Code:


::
  CK1&Dispatch
  BINT1
  ::
    ::
      %ABS
      COERCEDUP
      BINT2
      #<case
      DROPZERO
      DUP
      BINT4
      #<case
      #1-
      DUP
      # 690
      #>
      caseSIZEERR
      '
      ::
        BINT1
        #=casedrop
        ::
          #1+
          #2/
        ;
        2DUP
        #1-
        2GETEVAL
        ROT
        1GETLAM
        4PICK
        NTHCOMPDROP
        #/
        SWAPDROP
        ROT
        #1-
        2GETEVAL
        #-
      ;
      {
        BINT2
        BINT3
        BINT5
        BINT7
        BINT11
        BINT13
        2REAL
        BINT19
        BINT23
        BINT29
        BINT31
        BINT37
        BINT41
      }
      FPTR2 ^2LAMBIND
      DUP
      UNCOERCE
      %SQRT
      %IP
      COERCE
      1GETLAM
      SWAP'
      #>
      POSCOMP
      #1-DUP
      #1-UNROT
      2GETEVAL
      ABND
      #+
    ;
    UNCOERCE
  ;
;

[Gerald H]

An APPROXIMATE solution to the prime count question is given by Locker-Ernst's formula

p(n) ≈ n / ( H(n) - 3 / 2 )

H(n) the nth harmonic number.

In the programme below the harmonic number function is replaced by the HP 49G function Psi(n) (FPTR 7 11E is the Psi function for long reals), as Psi(n+1)+gamma gives H(n).

Code:


::
  CK1&Dispatch
  BINT1
  ::
    %>%%
    DUP
    %%1+_
    FPTR 7 11E
    %% 9.22784335098467E-1
    %%-
    %%/
    %%>%
  ;
;