Anti-primes: Difference between revisions
m (→{{header|REXX}}: elided REXX version 2.) |
|||
| Line 186: | Line 186: | ||
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> |
</pre> |
||
=={{header|Julia}}== |
|||
<lang julia>using Primes, Combinatorics |
|||
function antiprimes(N, max = 1000000) |
|||
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)) |
|||
</lang>{{output}}<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
Revision as of 10:13, 9 December 2018
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
<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
Factor
<lang factor>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</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 }
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
Julia
<lang julia>using Primes, Combinatorics
function antiprimes(N, max = 1000000)
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))
</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
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. <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*/ 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".*/</lang>
- 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
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