Anti-primes

From Rosetta Code
Task
Anti-primes
You are encouraged to solve this task according to the task description, using any language you may know.

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[edit]

Translation of: Go
#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;
}
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++[edit]

Translation of: C
#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;
}
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 

Factor[edit]

USING: assocs formatting kernel locals make math
math.primes.factors sequences.extras ;
IN: rosetta-code.anti-primes
 
<PRIVATE
 
: count-divisors ( n -- m )
dup 1 = [ group-factors values [ 1 + ] map-product ] unless ;
 
: (n-anti-primes) ( md n count -- ?md' n' ?count' )
dup 0 >
[| max-div! n count! |
n count-divisors :> d
d max-div > [ d max-div! n , count 1 - count! ] when
max-div n dup 60 >= 20 1 ? + count (n-anti-primes)
] when ;
 
PRIVATE>
 
: n-anti-primes ( n -- seq )
[ 0 1 ] dip [ (n-anti-primes) 3drop ] { } make ;
 
: anti-primes-demo ( -- )
20 n-anti-primes "First 20 anti-primes:\n%[%d, %]\n" printf ;
 
MAIN: anti-primes-demo
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 }

Go[edit]

Simple brute force approach which is quick enough here.

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()
}
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[edit]

Translation of: Go
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();
}
}
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 

Julia[edit]

using Primes, Combinatorics
 
function antiprimes(N, max = 2000000)
antip = [1] # special case: 1 is antiprime
count = 1
maxfactors = 1
for i in 2:2:max # antiprimes > 2 should be even
lenfac = length(unique(sort(collect(combinations(factor(Vector, i)))))) + 1
if lenfac > maxfactors
push!(antip, i)
if length(antip) >= N
return antip
end
maxfactors = lenfac
end
end
antip
end
 
println("The first 20 anti-primes are:\n", antiprimes(20))
println("The first 40 anti-primes are:\n", antiprimes(40))
 
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]
The first 40 anti-primes are:
[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 
10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, 221760, 277200, 
332640, 498960, 554400, 665280, 720720, 1081080, 1441440]

Kotlin[edit]

Translation of: Go
// 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()
}
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[edit]

Easy factoring without primes.Decided to show count of factors.

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.
;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[edit]

Works with: Rakudo version 2018.11

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.

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: {[email protected][^(@anti-primes.first: * > $upto, :k)]}";
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[edit]

Uses the fast prime function from Factors of an integer#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)))
Output:
[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560]

REXX[edit]

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).

The   #DIVS   function could be further optimized by only processing   even   numbers, with unity being treated as a special case.

/*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*/
say '─index─ ──anti─prime──' /*display a title for the numbers shown*/
#= 0 /*the count of anti─primes found " " */
do once=1 for 1
do i=1 for 59 /*step through possible numbers by twos*/
d= #divs(i); if d<=maxD then iterate /*get # divisors; Is too small? Skip.*/
#= # + 1; maxD= d /*found an anti─prime #; set new minD.*/
say center(#, 7) right(i, 10) /*display the index and the anti─prime.*/
if #>=N then leave once /*if we have enough anti─primes, done. */
end /*i*/
 
do j=60 by 20 /*step through possible numbers by 20. */
d= #divs(j); if d<=maxD then iterate /*get # divisors; Is too small? Skip.*/
#= # + 1; maxD= d /*found an anti─prime #; set new minD.*/
say center(#, 7) right(j, 10) /*display the index and the anti─prime.*/
if #>=N then leave once /*if we have enough anti─primes, done. */
end /*j*/
end /*once*/
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 cases 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".*/
output   when using the default input of:     20
─index─ ──anti─prime──
   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
output   when using the default input of:     55
─index─ ──anti─prime──
   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[edit]

Using the built-in Number.sigma0 method to count the number of divisors.

say with (0) {|max|
1..Inf -> lazy.grep { (.sigma0 > max) && (max = .sigma0) }.first(20)
}
Output:
[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560]

zkl[edit]

Translation of: Perl6
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
}
println("First 20 anti-primes:\n  ",antiPrimes().walk(20).concat(" "));
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