Piprimes

Piprimes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

pi(n), the number of primes <= n, where pi(n) < 22
Prime-counting_function
Tables and hints by Tomás Oliveira e Silva

Also see

•   the OEIS entry:   A0000720 pi(n), the number of primes <= n. Sometimes called PrimePi(n)....

REXX

<lang rexx>/*REXX program finds and displays pi(n) for 0 < N ≤ prime(22) {the 22nd prime is 87},*/ /*────────────────────────── where the pi function returns the number of primes ≤ N.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 22 /* " " " " " " */ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */ @pips= ' number of primes that are (for all N) ≤ prime(22) which is ' commas(@.hi) if cols>0 then say ' index │'center(@pips, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') idx= 1 /*initialize the index of output lines.*/ $=; pips= 0 /*a list of piPrimes numbers (so far). */

    do j=1  for @.hi-1                          /*gen list of piPrime numbers<prime(hi)*/
    if !.j  then pips= pips + 1                 /*Is J prime?  Then bump  pips  number.*/
    if cols==0           then iterate           /*Build the list  (to be shown later)? */
    c= commas(pips)                             /*maybe add commas to the number.      */
    $= $ right(c, max(w, length(c) ) )          /*add a Frobenius #──►list, allow big #*/
    if j//cols\==0   then iterate               /*have we populated a line of output?  */
    say center(idx, 7)'│'  substr($, 2);   $=   /*display what we have so far  (cols). */
    idx= idx + cols                             /*bump the  index  count for the output*/
    end   /*j*/

if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'Found ' commas(j-1)", the" @pips exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0 /*placeholders for primes (semaphores).*/

     @.1=2;  @.2=3;  @.3=5;  @.4=7;  @.5=11     /*define some low primes.              */
     !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1     /*   "     "   "    "     flags.       */
                       #=5;     s.#= @.# **2    /*number of primes so far;     prime². */
                                                /* [↓]  generate more  primes  ≤  high.*/
       do j=@.#+2  by 2  until #>hi             /*find odd primes from here on.        */
       parse var j  -1 _; if     _==5  then iterate  /*J divisible by 5?  (right dig)*/
                            if j// 3==0  then iterate  /*"     "      " 3?             */
                            if j// 7==0  then iterate  /*"     "      " 7?             */
                                                /* [↑]  the above  3  lines saves time.*/
              do k=5  while s.k<=j              /* [↓]  divide by the known odd primes.*/
              if j // @.k == 0  then iterate j  /*Is  J ÷ X?  Then not prime.     ___  */
              end   /*k*/                       /* [↑]  only process numbers  ≤  √ J   */
       #= #+1;    @.#= j;    s.#= j*j;   !.j= 1 /*bump # of Ps; assign next P;  P²; P# */
       end          /*j*/;   return</lang>

output   when using the default inputs:

 index │                      number of primes that are  (for all  N)  ≤  prime(22)   which is  79
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          0          1          2          2          3          3          4          4          4          4
  11   │          5          5          6          6          6          6          7          7          8          8
  21   │          8          8          9          9          9          9          9          9         10         10
  31   │         11         11         11         11         11         11         12         12         12         12
  41   │         13         13         14         14         14         14         15         15         15         15
  51   │         15         15         16         16         16         16         16         16         17         17
  61   │         18         18         18         18         18         18         19         19         19         19
  71   │         20         20         21         21         21         21         21         21

Found  78,  the  number of primes that are  (for all  N)  ≤  prime(22)   which is  79

Ring

<lang ring> load "stdlib.ring"

decimals(0) see "working..." + nl see "Piprimes are:" + nl

row = 0 limit1 = 400 Prim = []

for n = 1 to limit1

   if isprime(n)
      add(Prim,n)
   ok

next

for n = 1 to len(Prim)

   for m = 1 to len(Prim)
       if Prim[m] > n
          ind = m - 1
          exit
       ok
   next
   row = row + 1
   see "" + ind + " "
   if row%10 = 0
      see nl
   ok

next

see nl + "Found " + row + " Piprimes." + nl see "done..." + nl </lang>

Output:

working...
Piprimes are:
0 1 2 2 3 3 4 4 4 4 
5 5 6 6 6 6 7 7 8 8 
8 8 9 9 9 9 9 9 10 10 
11 11 11 11 11 11 12 12 12 12 
13 13 14 14 14 14 15 15 15 15 
15 15 16 16 16 16 16 16 17 17 
18 18 18 18 18 18 19 19 19 19 
20 20 21 21 21 21 21 21 
Found 78 Piprimes.
done...