Anti-primes: Difference between revisions
Content added Content deleted
(→version 1: changed the format of the output from horizontal to vertical.) |
m (→{{header|REXX}}: elided REXX version 2.) |
||
Line 345: | Line 345: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
|||
This REXX version is using a modified version of a highly optimized ''proper divisors'' function. |
This REXX version is using a modified version of a highly optimized ''proper divisors'' function. |
||
Programming note: although the solution to this Rosetta Code task is trivial, a fair amount of optimization was incorporated into the REXX program to find larger anti─primes (highly─composite numbers). |
Programming note: although the solution to this Rosetta Code task is trivial, a fair amount of optimization was incorporated into the REXX program to find larger anti─primes (highly─composite numbers). |
||
The #DIVS function could be further optimized by only processing ''even'' numbers, with unity being treated as a special case. |
|||
<lang rexx>/*REXX program finds N number of anti─primes or highly─composite numbers. */ |
<lang rexx>/*REXX program finds N number of anti─primes or highly─composite numbers. */ |
||
parse arg N . /*obtain optional argument from the CL.*/ |
parse arg N . /*obtain optional argument from the CL.*/ |
||
Line 413: | Line 414: | ||
</pre> |
</pre> |
||
===version 2=== |
|||
This REXX version takes advantage of the fact that anti─primes (highly─composite numbers) above 59 can be incremented by 20. |
|||
<lang rexx>/*REXX program finds N number of anti─primes or highly─composite numbers. */ |
|||
parse arg N . /*obtain optional argument from the CL.*/ |
|||
if N=='' | N=="," then N=55 /*Not specified? Then use the default.*/ |
|||
maxD= 0 /*the maximum number of divisors so far*/ |
|||
#= 0 /*the count of anti─primes found " " */ |
|||
$= /*the list of anti─primes found " " */ |
|||
do j=1 for 59 while #<N /*step through possible numbers by twos*/ |
|||
d= #divs(j) /*obtain the number of divisors for K.*/ |
|||
if d<=maxD then iterate /*Is D ≤ previous div count? Skip it. */ |
|||
#= # + 1; $= $ j /*found an anti─prime #, add it to list*/ |
|||
say right(#, 11) j |
|||
maxD= d /*use this as the new high─water mark. */ |
|||
end /*j*/ |
|||
do j=60 by 20 while #<N /*step through possible numbers by 20. */ |
|||
d= #divs(j) /*obtain the number of divisors for K.*/ |
|||
if d<=maxD then iterate /*Is D ≤ previous div count? Skip it. */ |
|||
#= # + 1; $= $ j /*found an anti─prime #, add it to list*/ |
|||
say right(#, 11) j |
|||
maxD= d /*use this as the new high─water mark. */ |
|||
end /*j*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
#divs: procedure; parse arg x 1 y /*X and Y: both set from 1st argument.*/ |
|||
if x<3 then return x /*handle special case for one and two. */ |
|||
if x==4 then return 3 /* " " " " four. */ |
|||
if x<6 then return 2 /* " " " " three or five*/ |
|||
odd= x // 2 /*check if X is odd or not. */ |
|||
if odd then do; #= 1; end /*Odd? Assume Pdivisors count of 1.*/ |
|||
else do; #= 3; y= x%2; end /*Even? " " " " 3.*/ |
|||
/* [↑] start with known num of Pdivs.*/ |
|||
do k=3 for x%2-3 by 1+odd while k<y /*for odd numbers, skip evens.*/ |
|||
if x//k==0 then do /*if no remainder, then found a divisor*/ |
|||
#=#+2; y=x%k /*bump # Pdivs, calculate limit Y. */ |
|||
if k>=y then do; #= #-1; leave; end /*limit?*/ |
|||
end /* ___ */ |
|||
else if k*k>x then leave /*only divide up to √ x */ |
|||
end /*k*/ /* [↑] this form of DO loop is faster.*/ |
|||
return #+1 /*bump "proper divisors" to "divisors".*/</lang> |
|||
{{out|output|text= when using the default input of: <tt> 55 </tt>}} |
{{out|output|text= when using the default input of: <tt> 55 </tt>}} |
||
<pre> |
<pre> |
||
─index─ ──anti─prime── |
|||
1 1 |
|||
1 1 |
|||
2 2 |
|||
3 4 |
|||
4 6 |
|||
5 12 |
|||
6 24 |
|||
7 36 |
|||
8 48 |
|||
9 60 |
|||
10 120 |
|||
11 180 |
|||
12 240 |
|||
13 360 |
|||
14 720 |
|||
15 840 |
|||
16 1260 |
|||
17 1680 |
|||
18 2520 |
|||
19 5040 |
|||
20 7560 |
|||
21 10080 |
|||
22 15120 |
|||
23 20160 |
|||
24 25200 |
|||
25 27720 |
|||
26 45360 |
|||
27 50400 |
|||
28 55440 |
|||
29 83160 |
|||
30 110880 |
|||
31 166320 |
|||
32 221760 |
|||
33 277200 |
|||
34 332640 |
|||
35 498960 |
|||
36 554400 |
|||
37 665280 |
|||
38 720720 |
|||
39 1081080 |
|||
40 1441440 |
|||
41 2162160 |
|||
42 2882880 |
|||
43 3603600 |
|||
44 4324320 |
|||
45 6486480 |
|||
46 7207200 |
|||
47 8648640 |
|||
48 10810800 |
|||
49 14414400 |
|||
50 17297280 |
|||
51 21621600 |
|||
52 32432400 |
|||
53 36756720 |
|||
54 43243200 |
|||
55 61261200 |
|||
</pre> |
</pre> |
||