Anti-primes: Difference between revisions
(Added Sidef) |
(Added Go) |
||
Line 10: | Line 10: | ||
;Related task: |
;Related task: |
||
::* [[Factors of an integer]] |
::* [[Factors of an integer]] |
||
=={{header|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> |
|||
{{out}} |
|||
<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|Pascal}}== |
=={{header|Pascal}}== |
||
Line 63: | Line 103: | ||
end.</lang>;Output:<pre>1(1),2(2),4(3),6(4),12(6),24(8),36(9),48(10),60(12),120(16),180(18),240(20), |
end.</lang>;Output:<pre>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)</pre> |
360(24),720(30),840(32),1260(36),1680(40),2520(48),5040(60),7560(64)</pre> |
||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
{{works with|Rakudo|2018.11}} |
{{works with|Rakudo|2018.11}} |
Revision as of 15:22, 6 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
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
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, *+30 … *).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: 36
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]
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]