⚠️ Warning: This is a draft ⚠️
This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.
If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.
{{task}} [[Category:Prime Numbers]]
The [https://youtu.be/2JM2oImb9Qg anti-primes] (or [https://en.wikipedia.org/wiki/Highly_composite_number highly composite numbers], sequence [https://oeis.org/A002182 A002182] in the [https://oeis.org/ OEIS]) are the natural numbers with more factors than any smaller than itself.
;Task: Generate and show here, the first twenty anti-primes.
;Related tasks:
[[Factors of an integer]]
[[Sieve of Eratosthenes]]
11l
V max_divisors = 0
V c = 0
V n = 1
L
V divisors = 1
L(i) 1 .. n I/ 2
I n % i == 0
divisors++
I divisors > max_divisors
max_divisors = divisors
print(n, end' ‘ ’)
c++
I c == 20
L.break
n++
{{out}}
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
Ada
with Ada.Text_IO; use Ada.Text_IO;
procedure Antiprimes is
function Count_Divisors (N : Integer) return Integer is
Count : Integer := 1;
begin
for i in 1 .. N / 2 loop
if N mod i = 0 then
Count := Count + 1;
end if;
end loop;
return Count;
end Count_Divisors;
Results : array (1 .. 20) of Integer;
Candidate : Integer := 1;
Divisors : Integer;
Max_Divisors : Integer := 0;
begin
for i in Results'Range loop
loop
Divisors := Count_Divisors (Candidate);
if Max_Divisors < Divisors then
Results (i) := Candidate;
Max_Divisors := Divisors;
exit;
end if;
Candidate := Candidate + 1;
end loop;
end loop;
Put_Line ("The first 20 anti-primes are:");
for I in Results'Range loop
Put (Integer'Image (Results (I)));
end loop;
New_Line;
end Antiprimes;
{{out}}
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
AWK
{{trans|Go}}
# syntax: GAWK -f ANTI-PRIMES.AWK
BEGIN {
print("The first 20 anti-primes are:")
while (count < 20) {
d = count_divisors(++n)
if (d > max_divisors) {
printf("%d ",n)
max_divisors = d
count++
}
}
printf("\n")
exit(0)
}
function count_divisors(n, count,i) {
if (n < 2) {
return(1)
}
count = 2
for (i=2; i<=n/2; i++) {
if (n % i == 0) {
count++
}
}
return(count)
}
{{out}}
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
BASIC256
Dim Results(20)
Candidate = 1
max_divisors = 0
Print "Los primeros 20 anti-primos son:"
For j = 0 To 19
Do
divisors = count_divisors(Candidate)
If max_divisors < divisors Then
Results[j] = Candidate
max_divisors = divisors
Exit Do
End If
Candidate += 1
Until false
Print Results[j];" ";
Next j
Function count_divisors(n)
cont = 1
For i = 1 To n/2
If (n % i) = 0 Then cont += 1
Next i
count_divisors = cont
End Function
{{out}}
Los primeros 20 anti-primos son:
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
C
{{trans|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; }
{{out}}
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++
{{trans|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; }
{{out}}
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#
{{works with|C sharp|7}}
using System; using System.Linq; using System.Collections.Generic; public static class Program { public static void Main() => Console.WriteLine(string.Join(" ", FindAntiPrimes().Take(20))); static IEnumerable<int> FindAntiPrimes() { int max = 0; for (int i = 1; ; i++) { int divisors = CountDivisors(i); if (divisors > max) { max = divisors; yield return i; } } int CountDivisors(int n) => Enumerable.Range(1, n / 2).Count(i => n % i == 0) + 1; } }
{{out}}
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
D
{{trans|C++}}
import std.stdio; 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; } void main() { int maxDiv, count; writeln("The first 20 anti-primes are:"); for (int n = 1; count < 20; ++n) { int d = countDivisors(n); if (d > maxDiv) { write(n, ' '); maxDiv = d; count++; } } writeln; }
{{out}}
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
Erlang
divcount(N) -> divcount(N, 1, 0). divcount(N, D, Count) when D*D > N -> Count; divcount(N, D, Count) -> Divs = case N rem D of 0 -> case N - D*D of 0 -> 1; _ -> 2 end; _ -> 0 end, divcount(N, D + 1, Count + Divs). antiprimes(N) -> antiprimes(N, 1, 0, []). antiprimes(0, _, _, L) -> lists:reverse(L); antiprimes(N, M, Max, L) -> Count = divcount(M), case Count > Max of true -> antiprimes(N-1, M+1, Count, [M|L]); false -> antiprimes(N, M+1, Max, L) end. main(_) -> io:format("The first 20 anti-primes are ~w~n", [antiprimes(20)]).
{{out}}
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
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
{{out}}
First 20 anti-primes:
{ 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560 }
FreeBASIC
' convertido desde Ada
Declare Function count_divisors(n As Integer) As Integer
Dim As Integer max_divisors, divisors, results(1 To 20), candidate, j
candidate = 1
Function count_divisors(n As Integer) As Integer
Dim As Integer i, count = 1
For i = 1 To n/2
If (n Mod i) = 0 Then count += 1
Next i
count_divisors = count
End Function
Print "Los primeros 20 anti-primos son:"
For j = 1 To 20
Do
divisors = count_divisors(Candidate)
If max_divisors < divisors Then
Results(j) = Candidate
max_divisors = divisors
Exit Do
End If
Candidate += 1
Loop
Next j
For j = 1 To 20
Print Results(j);
Next j
Print
Sleep
{{out}}
Los primeros 20 anti-primos son:
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560
=={{header|F_Sharp|F#}}==
The Function
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
// Find Antı-Primes. Nigel Galloway: Secember 10th., 2018 let N=200000000000000000000000000I let fI,_=Seq.scan(fun (_,g) e->(e,e*g)) (2I,4I) (primes|>Seq.skip 1|>Seq.map bigint)|>Seq.takeWhile(fun(_,n)->n<N)|>List.ofSeq|>List.unzip let fG g=Seq.unfold(fun ((n,i,e) as z)->Some(z,(n+1,i+1,(e*g)))) (1,2,g)|>Seq.takeWhile(fun(_,_,n)->n<N) let fE n i=n|>Seq.collect(fun(n,e,g)->Seq.map(fun(a,c,b)->(a,c*e,g*b)) (i|>Seq.takeWhile(fun(g,_,_)->g<=n)) |> Seq.takeWhile(fun(_,_,n)->n<N)) let fL,_=Seq.concat(Seq.scan(fun n g->fE n (fG g)) (seq[(2147483647,1,1I)]) fI)|>List.ofSeq|>List.sortBy(fun(_,_,n)->n)|>List.fold(fun ((a,b) as z) (_,n,g)->if n>b then ((n,g)::a,n) else z) ([],0)
The Task
printfn "The first 20 anti-primes are :-"; for (_,g) in (List.rev fL)|>List.take 20 do printfn "%A" g
{{out}}
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
Extra Credit
printfn "There are %d anti-primes less than %A:-" (List.length fL) N; for (n,g) in (List.rev fL) do printfn "%A has %d dividers" g n
{{out}}
There are 245 anti-primes less than 200000000000000000000000000:- 1 has 1 dividers 2 has 2 dividers 4 has 3 dividers 6 has 4 dividers 12 has 6 dividers 24 has 8 dividers 36 has 9 dividers 48 has 10 dividers 60 has 12 dividers 120 has 16 dividers 180 has 18 dividers 240 has 20 dividers 360 has 24 dividers 720 has 30 dividers 840 has 32 dividers 1260 has 36 dividers 1680 has 40 dividers 2520 has 48 dividers 5040 has 60 dividers 7560 has 64 dividers 10080 has 72 dividers 15120 has 80 dividers 20160 has 84 dividers 25200 has 90 dividers 27720 has 96 dividers 45360 has 100 dividers 50400 has 108 dividers 55440 has 120 dividers 83160 has 128 dividers 110880 has 144 dividers 166320 has 160 dividers 221760 has 168 dividers 277200 has 180 dividers 332640 has 192 dividers 498960 has 200 dividers 554400 has 216 dividers 665280 has 224 dividers 720720 has 240 dividers 1081080 has 256 dividers 1441440 has 288 dividers 2162160 has 320 dividers 2882880 has 336 dividers 3603600 has 360 dividers 4324320 has 384 dividers 6486480 has 400 dividers 7207200 has 432 dividers 8648640 has 448 dividers 10810800 has 480 dividers 14414400 has 504 dividers 17297280 has 512 dividers 21621600 has 576 dividers 32432400 has 600 dividers 36756720 has 640 dividers 43243200 has 672 dividers 61261200 has 720 dividers 73513440 has 768 dividers 110270160 has 800 dividers 122522400 has 864 dividers 147026880 has 896 dividers 183783600 has 960 dividers 245044800 has 1008 dividers 294053760 has 1024 dividers 367567200 has 1152 dividers 551350800 has 1200 dividers 698377680 has 1280 dividers 735134400 has 1344 dividers 1102701600 has 1440 dividers 1396755360 has 1536 dividers 2095133040 has 1600 dividers 2205403200 has 1680 dividers 2327925600 has 1728 dividers 2793510720 has 1792 dividers 3491888400 has 1920 dividers 4655851200 has 2016 dividers 5587021440 has 2048 dividers 6983776800 has 2304 dividers 10475665200 has 2400 dividers 13967553600 has 2688 dividers 20951330400 has 2880 dividers 27935107200 has 3072 dividers 41902660800 has 3360 dividers 48886437600 has 3456 dividers 64250746560 has 3584 dividers 73329656400 has 3600 dividers 80313433200 has 3840 dividers 97772875200 has 4032 dividers 128501493120 has 4096 dividers 146659312800 has 4320 dividers 160626866400 has 4608 dividers 240940299600 has 4800 dividers 293318625600 has 5040 dividers 321253732800 has 5376 dividers 481880599200 has 5760 dividers 642507465600 has 6144 dividers 963761198400 has 6720 dividers 1124388064800 has 6912 dividers 1606268664000 has 7168 dividers 1686582097200 has 7200 dividers 1927522396800 has 7680 dividers 2248776129600 has 8064 dividers 3212537328000 has 8192 dividers 3373164194400 has 8640 dividers 4497552259200 has 9216 dividers 6746328388800 has 10080 dividers 8995104518400 has 10368 dividers 9316358251200 has 10752 dividers 13492656777600 has 11520 dividers 18632716502400 has 12288 dividers 26985313555200 has 12960 dividers 27949074753600 has 13440 dividers 32607253879200 has 13824 dividers 46581791256000 has 14336 dividers 48910880818800 has 14400 dividers 55898149507200 has 15360 dividers 65214507758400 has 16128 dividers 93163582512000 has 16384 dividers 97821761637600 has 17280 dividers 130429015516800 has 18432 dividers 195643523275200 has 20160 dividers 260858031033600 has 20736 dividers 288807105787200 has 21504 dividers 391287046550400 has 23040 dividers 577614211574400 has 24576 dividers 782574093100800 has 25920 dividers 866421317361600 has 26880 dividers 1010824870255200 has 27648 dividers 1444035528936000 has 28672 dividers 1516237305382800 has 28800 dividers 1732842634723200 has 30720 dividers 2021649740510400 has 32256 dividers 2888071057872000 has 32768 dividers 3032474610765600 has 34560 dividers 4043299481020800 has 36864 dividers 6064949221531200 has 40320 dividers 8086598962041600 has 41472 dividers 10108248702552000 has 43008 dividers 12129898443062400 has 46080 dividers 18194847664593600 has 48384 dividers 20216497405104000 has 49152 dividers 24259796886124800 has 51840 dividers 30324746107656000 has 53760 dividers 36389695329187200 has 55296 dividers 48519593772249600 has 57600 dividers 60649492215312000 has 61440 dividers 72779390658374400 has 62208 dividers 74801040398884800 has 64512 dividers 106858629141264000 has 65536 dividers 112201560598327200 has 69120 dividers 149602080797769600 has 73728 dividers 224403121196654400 has 80640 dividers 299204161595539200 has 82944 dividers 374005201994424000 has 86016 dividers 448806242393308800 has 92160 dividers 673209363589963200 has 96768 dividers 748010403988848000 has 98304 dividers 897612484786617600 has 103680 dividers 1122015605983272000 has 107520 dividers 1346418727179926400 has 110592 dividers 1795224969573235200 has 115200 dividers 2244031211966544000 has 122880 dividers 2692837454359852800 has 124416 dividers 3066842656354276800 has 129024 dividers 4381203794791824000 has 131072 dividers 4488062423933088000 has 138240 dividers 6133685312708553600 has 147456 dividers 8976124847866176000 has 153600 dividers 9200527969062830400 has 161280 dividers 12267370625417107200 has 165888 dividers 15334213281771384000 has 172032 dividers 18401055938125660800 has 184320 dividers 27601583907188491200 has 193536 dividers 30668426563542768000 has 196608 dividers 36802111876251321600 has 207360 dividers 46002639845314152000 has 215040 dividers 55203167814376982400 has 221184 dividers 73604223752502643200 has 230400 dividers 92005279690628304000 has 245760 dividers 110406335628753964800 has 248832 dividers 131874234223233902400 has 258048 dividers 184010559381256608000 has 276480 dividers 263748468446467804800 has 294912 dividers 368021118762513216000 has 307200 dividers 395622702669701707200 has 322560 dividers 527496936892935609600 has 331776 dividers 659371171116169512000 has 344064 dividers 791245405339403414400 has 368640 dividers 1186868108009105121600 has 387072 dividers 1318742342232339024000 has 393216 dividers 1582490810678806828800 has 414720 dividers 1978113513348508536000 has 430080 dividers 2373736216018210243200 has 442368 dividers 3164981621357613657600 has 460800 dividers 3956227026697017072000 has 491520 dividers 4747472432036420486400 has 497664 dividers 5934340540045525608000 has 516096 dividers 7912454053394034144000 has 552960 dividers 11868681080091051216000 has 589824 dividers 15824908106788068288000 has 614400 dividers 17407398917466875116800 has 622080 dividers 18594267025475980238400 has 645120 dividers 23737362160182102432000 has 663552 dividers 30990445042459967064000 has 688128 dividers 34814797834933750233600 has 691200 dividers 37188534050951960476800 has 737280 dividers 52222196752400625350400 has 746496 dividers 55782801076427940715200 has 774144 dividers 61980890084919934128000 has 786432 dividers 74377068101903920953600 has 829440 dividers 92971335127379901192000 has 860160 dividers 111565602152855881430400 has 884736 dividers 148754136203807841907200 has 921600 dividers 185942670254759802384000 has 983040 dividers 223131204305711762860800 has 995328 dividers 278914005382139703576000 has 1032192 dividers 371885340509519604768000 has 1105920 dividers 557828010764279407152000 has 1179648 dividers 743770681019039209536000 has 1228800 dividers 818147749120943130489600 has 1244160 dividers 985496152350226952635200 has 1290240 dividers 1115656021528558814304000 has 1327104 dividers 1487541362038078419072000 has 1351680 dividers 1636295498241886260979200 has 1382400 dividers 1970992304700453905270400 has 1474560 dividers 2454443247362829391468800 has 1492992 dividers 2956488457050680857905600 has 1548288 dividers 3284987174500756508784000 has 1572864 dividers 3941984609400907810540800 has 1658880 dividers 4927480761751134763176000 has 1720320 dividers 5912976914101361715811200 has 1769472 dividers 7883969218801815621081600 has 1843200 dividers 9854961523502269526352000 has 1966080 dividers 11825953828202723431622400 has 1990656 dividers 14782442285253404289528000 has 2064384 dividers 19709923047004539052704000 has 2211840 dividers 29564884570506808579056000 has 2359296 dividers 39419846094009078105408000 has 2457600 dividers 43361830703409985915948800 has 2488320 dividers 54202288379262482394936000 has 2580480 dividers 59129769141013617158112000 has 2654208 dividers 78839692188018156210816000 has 2703360 dividers 86723661406819971831897600 has 2764800 dividers 108404576758524964789872000 has 2949120 dividers 130085492110229957747846400 has 2985984 dividers 162606865137787447184808000 has 3096576 dividers 193814243295544634018256000 has 3145728 dividers ``` ## Go Simple brute force approach which is quick enough here. ```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() } ``` {{out}} ```txt 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 ``` ## Groovy Solution (uses [[Factors_of_an_integer#Groovy|Factors of an integer]] function "factorize()"): ```groovy def getAntiPrimes(def limit = 10) { def antiPrimes = [] def candidate = 1L def maxFactors = 0 while (antiPrimes.size() < limit) { def factors = factorize(candidate) if (factors.size() > maxFactors) { maxFactors = factors.size() antiPrimes << candidate } candidate++ } antiPrimes } ``` Test: ```groovy println (getAntiPrimes(20)) ``` Output: ```txt [1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560] ``` ## Haskell ```haskell import Data.List (find, group) import Data.Maybe (fromJust) firstPrimeFactor :: Int -> Int firstPrimeFactor n = head $ filter ((0 ==) . mod n) [2 .. n] allPrimeFactors :: Int -> [Int] allPrimeFactors 1 = [] allPrimeFactors n = let first = firstPrimeFactor n in first : allPrimeFactors (n `div` first) factorCount :: Int -> Int factorCount 1 = 1 factorCount n = product ((succ . length) <$> group (allPrimeFactors n)) divisorCount :: Int -> (Int, Int) divisorCount = (,) <*> factorCount hcnNext :: (Int, Int) -> (Int, Int) hcnNext (num, factors) = fromJust $ find ((> factors) . snd) (divisorCount <$> [num ..]) hcnSequence :: [Int] hcnSequence = fst <$> iterate hcnNext (1, 1) main :: IO () main = print $ take 20 hcnSequence ``` {{output}} ```txt [1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560] ``` ## J ```J NB. factor count is the product of the incremented powers of prime factors factor_count =: [: */ [: >: _&q: NB. N are the integers 1 to 10000 NB. FC are the corresponding factor counts FC =: factor_count&> N=: >: i. 10000 NB. take from the integers N{~ NB. the indexes of truth I. NB. the vector which doesn't equal itself when rotated by one position (~: _1&|.) NB. where that vector is the maximum over all prefixes of the factor counts >./\FC N{~I.(~: _1&|.)>./\FC 1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560 ``` ## Java {{trans|Go}} ```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(); } } ``` {{output}} ```txt 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 ``` ## Javascript ```javascript function factors(n) { var factors = []; for (var i = 1; i <= n; i++) { if (n % i == 0) { factors.push(i); } } return factors; } function generateAntiprimes(n) { var antiprimes = []; var maxFactors = 0; for (var i = 1; antiprimes.length < n; i++) { var ifactors = factors(i); if (ifactors.length > maxFactors) { antiprimes.push(i); maxFactors = ifactors.length; } } return antiprimes; } function go() { var number = document.getElementById("n").value; document.body.removeChild(document.getElementById("result-list")); document.body.appendChild(showList(generateAntiprimes(number))); } function showList(array) { var list = document.createElement("ul"); list.id = "result-list"; for (var i = 0; i < array.length; i++) { var item = document.createElement("li"); item.appendChild(document.createTextNode(array[i])); list.appendChild(item); } return list; } ``` Html to test with some styling ```txtAnti-Primes Anti-Primes
The anti-primes (or highly composite numbers, sequence A002182 in the OEIS) are the natural numbers with more factors than any smaller than itself.Generate first anti-primes.