Numbers whose count of divisors is prime
- Task
Find positive integers n which count of divisors is prime, but not equal to 2, where n < 1,000.
REXX
<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
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>
- Output:
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...