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