Anti-primes: Difference between revisions
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: | Line 312: | ||
=={{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. |
||
| Line 351: | Line 352: | ||
The first 20 anti─primes (highly─composite numbers) are: |
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 |
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> |
</pre> |
||
Revision as of 00:34, 8 December 2018
The anti-primes (or highly composite numbers) are the natural numbers with more factors than any smaller than itself.
- Task
Generate and show here, the first twenty anti-primes.
- Related task
C
<lang c>#include <stdio.h>
int countDivisors(int n) {
int i, count;
if (n < 2) return 1;
count = 2; // 1 and n
for (i = 2; i <= n/2; ++i) {
if (n%i == 0) ++count;
}
return count;
}
int main() {
int n, d, maxDiv = 0, count = 0;
printf("The first 20 anti-primes are:\n");
for (n = 1; count < 20; ++n) {
d = countDivisors(n);
if (d > maxDiv) {
printf("%d ", n);
maxDiv = d;
count++;
}
}
printf("\n");
return 0;
}</lang>
- Output:
The first 20 anti-primes are: 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
C++
<lang cpp>#include <iostream>
int countDivisors(int n) {
if (n < 2) return 1;
int count = 2; // 1 and n
for (int i = 2; i <= n/2; ++i) {
if (n%i == 0) ++count;
}
return count;
}
int main() {
int maxDiv = 0, count = 0;
std::cout << "The first 20 anti-primes are:" << std::endl;
for (int n = 1; count < 20; ++n) {
int d = countDivisors(n);
if (d > maxDiv) {
std::cout << n << " ";
maxDiv = d;
count++;
}
}
std::cout << std::endl;
return 0;
}</lang>
- Output:
The first 20 anti-primes are: 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
Go
Simple brute force approach which is quick enough here. <lang go>package main
import "fmt"
func countDivisors(n int) int {
if n < 2 {
return 1
}
count := 2 // 1 and n
for i := 2; i <= n/2; i++ {
if n%i == 0 {
count++
}
}
return count
}
func main() {
fmt.Println("The first 20 anti-primes are:")
maxDiv := 0
count := 0
for n := 1; count < 20; n++ {
d := countDivisors(n)
if d > maxDiv {
fmt.Printf("%d ", n)
maxDiv = d
count++
}
}
fmt.Println()
}</lang>
- Output:
The first 20 anti-primes are: 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
Java
<lang java>public class Antiprime {
static int countDivisors(int n) {
if (n < 2) return 1;
int count = 2; // 1 and n
for (int i = 2; i <= n/2; ++i) {
if (n%i == 0) ++count;
}
return count;
}
public static void main(String[] args) {
int maxDiv = 0, count = 0;
System.out.println("The first 20 anti-primes are:");
for (int n = 1; count < 20; ++n) {
int d = countDivisors(n);
if (d > maxDiv) {
System.out.printf("%d ", n);
maxDiv = d;
count++;
}
}
System.out.println();
}
}</lang>
- Output:
The first 20 anti-primes are: 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
Kotlin
<lang scala>// Version 1.3.10
fun countDivisors(n: Int): Int {
if (n < 2) return 1;
var count = 2 // 1 and n
for (i in 2..n / 2) {
if (n % i == 0) count++
}
return count;
}
fun main(args: Array<String>) {
println("The first 20 anti-primes are:")
var maxDiv = 0
var count = 0
var n = 1
while (count < 20) {
val d = countDivisors(n)
if (d > maxDiv) {
print("$n ")
maxDiv = d
count++
}
n++
}
println()
}</lang>
- Output:
The first 20 anti-primes are: 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
Pascal
Easy factoring without primes.Decided to show count of factors. <lang pascal>program AntiPrimes; {$IFdef FPC}
{$MOde Delphi}
{$IFEND} function getFactorCnt(n:NativeUint):NativeUint; var
divi,quot,pot,lmt : NativeUint;
begin
result := 1;
divi := 1;
lmt := trunc(sqrt(n));
while divi < n do
Begin
inc(divi);
pot := 0;
repeat
quot := n div divi;
if n <> quot*divi then
BREAK;
n := quot;
inc(pot);
until false;
result := result*(1+pot);
//IF n= prime leave now
if divi > lmt then
BREAK;
end;
end;
var
i,Count,FacCnt,lastCnt: NativeUint;
begin
count := 0;
lastCnt := 0;
i := 1;
repeat
FacCnt := getFactorCnt(i);
if lastCnt < FacCnt then
Begin
write(i,'(',FacCnt,'),');
lastCnt:= FacCnt;
inc(Count);
if count = 12 then
Writeln;
end;
inc(i);
until Count >= 20;
writeln;
end.</lang>;Output:
1(1),2(2),4(3),6(4),12(6),24(8),36(9),48(10),60(12),120(16),180(18),240(20), 360(24),720(30),840(32),1260(36),1680(40),2520(48),5040(60),7560(64)
Perl 6
At its heart, this task is almost exactly the same as Proper_Divisors, it is just asking for slightly different results. Much of this code is lifted straight from there.
Implemented as an auto-extending lazy list. Displaying the count of anti-primes less than 5e5 also because... why not.
<lang perl6>sub propdiv (\x) {
my @l = 1 if x > 1;
(2 .. x.sqrt.floor).map: -> \d {
unless x % d { @l.push: d; my \y = x div d; @l.push: y if y != d }
}
@l
}
my atomicint $last = 0;
my @anti-primes = lazy 1, |(|(2..59), 60, *+60 … *).hyper.grep: -> $c {
my \mx = +propdiv($c); next if mx <= $last; $last = mx; $c
}
my $upto = 5e5;
put "First 20 anti-primes:\n{ @anti-primes[^20] }";
put "\nCount of anti-primes <= $upto: {+@anti-primes[^(@anti-primes.first: * > $upto, :k)]}";</lang>
- Output:
First 20 anti-primes: 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560 Count of anti-primes <= 500000: 35
Python
Uses the fast prime function from Factors of an integer#Python <lang python>from itertools import chain, count, cycle, islice, accumulate
def factors(n):
def prime_powers(n):
for c in accumulate(chain([2, 1, 2], cycle([2,4]))):
if c*c > n: break
if n%c: continue
d,p = (), c
while not n%c:
n,p,d = n//c, p*c, d + (p,)
yield(d)
if n > 1: yield((n,))
r = [1]
for e in prime_powers(n):
r += [a*b for a in r for b in e]
return r
def antiprimes():
mx = 0
for c in count(1):
ln = len(factors(c))
if ln > mx:
yield c
mx = ln
if __name__ == '__main__':
print(list(islice(antiprimes(), 20)))</lang>
- Output:
[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560]
REXX
version 1
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). <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=20 /*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 until #==N; 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*/
maxD= d /*use this as the new high─water mark. */
end /*j*/
say say 'The first ' N " anti─primes (highly─composite numbers) are:" say strip($) 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>
- output when using the default input of: 20
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
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>
- output when using the default input of: 55
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
Sidef
Using the built-in Number.sigma0 method to count the number of divisors. <lang ruby>say with (0) {|max|
1..Inf -> lazy.grep { (.sigma0 > max) && (max = .sigma0) }.first(20)
}</lang>
- Output:
[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560]
zkl
<lang zkl>fcn properDivsN(n) //--> count of proper divisors. 1-->1, wrong but OK here
{ [1.. (n + 1)/2 + 1].reduce('wrap(p,i){ p + (n%i==0 and n!=i) }) }
fcn antiPrimes{ // -->iterator
Walker.chain([2..59],[60..*,30]).tweak(fcn(c,rlast){
last,mx := rlast.value, properDivsN(c);
if(mx<=last) return(Void.Skip);
rlast.set(mx);
c
}.fp1(Ref(0))).push(1); // 1 has no proper divisors
}</lang> <lang zkl>println("First 20 anti-primes:\n ",antiPrimes().walk(20).concat(" "));</lang>
- Output:
First 20 anti-primes: 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560