Anti-primes: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m →{{header|Perl 6}}: Typo, minor opt |
m →{{header|REXX}}: added REXX version 2 (that takes advantage of optimization by larger incrementation). |
||
Line 312:
=={{header|REXX}}==
===version 1===
This REXX version is using a modified version of a highly optimized ''proper divisors'' function.
Line 351 ⟶ 352:
The first 20 anti─primes (highly─composite numbers) are:
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
</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>}}
<pre>
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>
|