Anti-primes: Difference between revisions
m →{{header|REXX}}: changed a comment. |
Thundergnat (talk | contribs) m →{{header|Perl 6}}: Typo, minor opt |
||
Line 259:
my atomicint $last = 0;
my @anti-primes = lazy 1, |(|(2..59), 60, *+
my \mx = +propdiv($c);
next if mx <= $last;
Line 275:
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:
=={{header|Python}}==
|
Revision as of 21:23, 7 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
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
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