Numbers whose count of divisors is prime: Difference between revisions
m (added closing tag for PRE.) |
m (added closingHTML tag for PRE.) |
||
Line 88: | Line 88: | ||
Found 79 positive integers N whose number of divisors is prime, where N < 100,000 |
Found 79 positive integers N whose number of divisors is prime, where N < 100,000 |
||
<pre> |
</pre> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
Revision as of 04:29, 11 July 2021
- 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
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...