Numbers whose count of divisors is prime

Numbers whose count of divisors is prime 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

Find positive integers   n   which count of divisors is prime,   but not equal to  2,   where   n   <   1,000.

Stretch goal:   (as above),   but where   n   <   100,000.

REXX

Some optimization was added so as to bypass finding divisors for primes. <lang rexx>/*REXX pgm finds positive integers N whose count of divisors is prime, where N < 1000.*/ parse arg hi cols . /*obtain optional arguments from the CL*/ if hi== | hi=="," then hi= 1000 /*Not specified? Then use the defaults*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*W: the maximum width of any column. */ title= ' positive integers N whose number of divisors is prime, where N < ' commas(hi) say ' index │'center(title, 1 + cols*(w+1) ) say '───────┼'center("" , 1 + cols*(w+1), '─') finds= 0; idx= 1; $=

        do j=1  for hi-1                        /*process positive integers in range.  */
        if !.j  then iterate                    /*Is  J  prime?  Then skip this number.*/
                else do;  n= nDivs(j)           /*get number of divisors of composite J*/
                          if n==2  then iterate
                          if \!.n  then iterate /*Number divisors prime?  No, then skip*/
                     end
        finds= finds + 1                        /*bump the number of found numbers.    */
        $= $  right( commas(j),  w)             /*add a positive integer  ──►  $ list. */
        if finds//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*/                             /* [↑]   process a range of integers.  */

if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(finds) title 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 ? /*──────────────────────────────────────────────────────────────────────────────────────*/ nDivs: procedure; parse arg x; d= 2; if x==1 then return 1 /*handle special case of 1*/

      odd= x // 2                               /* [↓]  process EVEN or ODD ints.   ___*/
             do j=2+odd  by 1+odd  while j*j<x  /*divide by all the integers up to √ x */
             if x//j==0  then d= d + 2          /*÷?  Add two divisors to the total.   */
             end   /*j*/                        /* [↑]  %  ≡  integer division.        */
      if j*j==x  then  return  d + 1            /*Was X a square?  Then add 1 to total.*/
                       return  d                /*return the total.                    */

/*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */

     !.=0;  !.2=1; !.3=1; !.5=1; !.7=1;  !.11=1 /*   "     "   "    "     semaphores.  */
                          #=5;   s.#= @.# **2   /*number of primes so far;     prime². */
       do j=@.#+2  by 2  to hi-1                /*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?             */
              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 │                  positive integers  N  whose number of divisors is prime,  where  N <  1,000
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          4          9         16         25         49         64         81        121        169        289
  11   │        361        529        625        729        841        961
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────

Found  16  positive integers  N  whose number of divisors is prime,  where  N <  1,000

output   when using the input of:     100000

 index │                 positive integers  N  whose number of divisors is prime,  where  N <  100,000
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          4          9         16         25         49         64         81        121        169        289
  11   │        361        529        625        729        841        961      1,024      1,369      1,681      1,849
  21   │      2,209      2,401      2,809      3,481      3,721      4,096      4,489      5,041      5,329      6,241
  31   │      6,889      7,921      9,409     10,201     10,609     11,449     11,881     12,769     14,641     15,625
  41   │     16,129     17,161     18,769     19,321     22,201     22,801     24,649     26,569     27,889     28,561
  51   │     29,929     32,041     32,761     36,481     37,249     38,809     39,601     44,521     49,729     51,529
  61   │     52,441     54,289     57,121     58,081     59,049     63,001     65,536     66,049     69,169     72,361
  71   │     73,441     76,729     78,961     80,089     83,521     85,849     94,249     96,721     97,969
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────

Found  79  positive integers  N  whose number of divisors is prime,  where  N <  100,000

=={{header|Ring}}==
<lang ring>
load "stdlib.ring"
row = 0

see "working..." + nl
see "Numbers which count of divisors is prime are:" + nl

for n = 1 to 1000
    num = 0
    for m = 1 to n
        if n%m = 0
           num++
        ok
    next
    if isprime(num) and num != 2
       see "" + n + " "
       row++
       if row%5 = 0
          see nl
       ok
    ok  
next

see nl + "Found " + row + " numbers" + nl
see "done..." + nl
</lang>
{{out}}
<pre>
working...
Numbers which count of divisors is prime are:
4 9 16 25 49 
64 81 121 169 289 
361 529 625 729 841 
961 
Found 16 numbers
done...