Proper divisors: Difference between revisions
→{{header|langur}}
Langurmonkey (talk | contribs) |
|||
(113 intermediate revisions by 40 users not shown) | |||
Line 1:
{{task|Prime Numbers}}
The [http://planetmath.org/properdivisor proper divisors] of a positive integer '''N''' are those numbers, other than '''N''' itself, that divide '''N''' without remainder.
Line 26:
* [[Prime decomposition]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F proper_divs(n)
R Array(Set((1 .. (n + 1) I/ 2).filter(x -> @n % x == 0 & @n != x)))
print((1..10).map(n -> proper_divs(n)))
V (n, leng) = max(((1..20000).map(n -> (n, proper_divs(n).len))), key' pd -> pd[1])
print(n‘ ’leng)</syntaxhighlight>
{{out}}
<pre>
[[], [1], [1], [1, 2], [1], [1, 2, 3], [1], [1, 2, 4], [1, 3], [1, 2, 5]]
15120 79
</pre>
=={{header|360 Assembly}}==
{{trans|Rexx}}
This program uses two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.
<
PROPDIV CSECT
USING PROPDIV,R13 base register
Line 163 ⟶ 180:
XDEC DS CL12
YREGS
END PROPDIV</
{{out}}
<pre>
Line 177 ⟶ 194:
10 has 3 proper divisors: 1 2 5
15120 has 79 proper divisors.
</pre>
=={{header|Action!}}==
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.
<syntaxhighlight lang="action!">BYTE FUNC GetDivisors(INT a INT ARRAY divisors)
INT i,max
BYTE count
max=a/2
count=0
FOR i=1 TO max
DO
IF a MOD i=0 THEN
divisors(count)=i
count==+1
FI
OD
RETURN (count)
PROC Main()
DEFINE MAXNUM="20000"
INT i,j,count,max,ind
INT ARRAY divisors(100)
BYTE ARRAY pdc(MAXNUM+1)
FOR i=1 TO 10
DO
count=GetDivisors(i,divisors)
PrintF("%I has %I proper divisors: [",i,count)
FOR j=0 TO count-1
DO
PrintI(divisors(j))
IF j<count-1 THEN
Put(32)
FI
OD
PrintE("]")
OD
PutE() PrintE("Searching for max number of divisors:")
FOR i=1 TO MAXNUM
DO
pdc(i)=1
OD
FOR i=2 TO MAXNUM
DO
FOR j=i+i TO MAXNUM STEP i
DO
pdc(j)==+1
OD
OD
max=0 ind=0
FOR i=1 TO MAXNUM
DO
count=pdc(i)
IF count>max THEN
max=count ind=i
FI
OD
PrintF("%I has %I proper divisors%E",ind,max)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Proper_divisors.png Screenshot from Atari 8-bit computer]
<pre>
1 has 0 proper divisors: []
2 has 1 proper divisors: [1]
3 has 1 proper divisors: [1]
4 has 2 proper divisors: [1 2]
5 has 1 proper divisors: [1]
6 has 3 proper divisors: [1 2 3]
7 has 1 proper divisors: [1]
8 has 3 proper divisors: [1 2 4]
9 has 2 proper divisors: [1 3]
10 has 3 proper divisors: [1 2 5]
Searching for max number of divisors:
15120 has 79 proper divisors
</pre>
=={{header|Ada}}==
The first part of the task is to
[[http://rosettacode.org/wiki/Abundant,_deficient_and_perfect_number_classifications#Ada]],
''Abundant Odd Number''
[[http://rosettacode.org/wiki/Abundant_odd_numbers#Ada]],
and ''Amicable Pairs''
[[http://rosettacode.org/wiki/Amicable_pairs#Ada]], we define this routine as a function of a generic package:
<
type Result_Type (<>) is limited private;
None: Result_Type;
Line 200 ⟶ 301:
else Process(N, First+1));
end Generic_Divisors;</
Now we instantiate the ''generic package'' to solve the other two parts of the task. Observe that there are two different instantiations of the package: one to generate a list of proper divisors, another one to count the number of proper divisors without actually generating such a list:
<
procedure Proper_Divisors is
Line 215 ⟶ 316:
Empty: Pos_Arr(1 .. 0);
function Arr(P: Positive) return Single_Pos_Arr is ((others =>
package Divisor_List is new Generic_Divisors
Line 266 ⟶ 363:
Natural'Image(Number_Count) & " proper divisors.");
end;
end Proper_Divisors; </
{{out}}
Line 272 ⟶ 369:
2 has 1 proper divisors: 1
3 has 1 proper divisors: 1
4 has 2 proper divisors: 1
5 has 1 proper divisors: 1
6 has 3 proper divisors: 1
7 has 1 proper divisors: 1
8 has 3 proper divisors: 1
9 has 2 proper divisors: 1
10 has 3 proper divisors: 1
15120 has the maximum number of 79 proper divisors.</pre>
=={{header|ALGOL 68}}==
===As required by the Task===
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<
MODE DIVISORLIST = STRUCT( INT divisor, REF DIVISORLIST next );
Line 374 ⟶ 473:
, " divisors"
, newline
) )</
{{out}}
<pre>
Line 390 ⟶ 489:
</pre>
===Faster Proper Divisor Counting===
Alternative version that uses a sieve-like approach for faster proper divisor counting.
<br><br>Note, in order to run this with Algol 68G under Windows (and possibly Linux) the heap size must be increased, see [[ALGOL_68_Genie#Using_a_Large_Heap]].
<syntaxhighlight lang="algol68">BEGIN # count proper divisors using a sieve-like approach #
# find the first/only number in 1 : 20 000 and 1 : 64 000 000 with #
# the most divisors #
INT max number := 20 000;
TO 2 DO
INT max divisors := 0;
INT has max divisors := 0;
INT with max divisors := 0;
[ 1 : max number ]INT pdc; pdc[ 1 ] := 0; FOR i FROM 2 TO UPB pdc DO pdc[ i ] := 1 OD;
FOR i FROM 2 TO UPB pdc DO
FOR j FROM i + i BY i TO UPB pdc DO pdc[ j ] +:= 1 OD
OD;
FOR d TO max number DO
INT divisor count = pdc[ d ];
IF divisor count > max divisors THEN
# found a number with more divisors than the previous max #
max divisors := divisor count;
has max divisors := d;
with max divisors := 1
ELIF divisor count = max divisors THEN
# found another number with that many divisors #
with max divisors +:= 1
FI
OD;
print( ( whole( has max divisors, 0 )
, " is the "
, IF with max divisors < 2 THEN "only" ELSE "first" FI
, " number upto "
, whole( max number, 0 )
, " with "
, whole( max divisors, 0 )
, " divisors"
, newline
)
);
max number := 64 000 000
OD
END</syntaxhighlight>
{{out}}
<pre>
15120 is the first number upto 20000 with 79 divisors
61261200 is the only number upto 64000000 with 719 divisors
</pre>
=={{header|ALGOL-M}}==
Algol-M's maximum allowed integer value of 16,383 prevented searching up to 20,000 for the number with the most divisors, so the code here searches only up to 10,000.
<
BEGIN
Line 417 ⟶ 564:
DELTA := 2;
END;
% 1 IS
IF N > 1 THEN COUNT := 1 ELSE COUNT := 0;
IF (DISPLAY <> 0) AND (COUNT <> 0) THEN WRITEON(1);
% CHECK REMAINING POTENTIAL DIVISORS %
I := START;
Line 449 ⟶ 595:
END;
WRITE("SEARCHING FOR NUMBER UP TO 10000 WITH MOST DIVISORS ...");
HIGHDIV := 1;
HIGHNUM := 1;
Line 465 ⟶ 611:
END
</syntaxhighlight>
{{out}}
<pre>
PROPER DIVISORS OF FIRST TEN NUMBERS:
1 :
2 : 1
3 : 1
Line 479 ⟶ 625:
9 : 1 3
10 : 1 2 5
SEARCHING FOR NUMBER UP TO 10000 WITH MOST DIVISORS:
THE NUMBER IS: 7560
IT HAS 63 DIVISORS
</pre>
=={{header|AppleScript}}==
===Functional===
{{Trans|JavaScript}}
<
-- properDivisors :: Int -> [Int]
Line 616 ⟶ 762:
end script
end if
end mReturn</
{{Out}}
<
{num:4, divisors:{1, 2}}, {num:5, divisors:{1}}, {num:6, divisors:{1, 2, 3}},
{num:7, divisors:{1}}, {num:8, divisors:{1, 2, 4}}, {num:9, divisors:{1, 3}},
{num:10, divisors:{1, 2, 5}}},
mostDivisors:{num:18480, divisors:79}}</
----
===Idiomatic===
<syntaxhighlight lang="applescript">on properDivisors(n)
set output to {}
if (n > 1) then
set sqrt to n ^ 0.5
set limit to sqrt div 1
if (limit = sqrt) then
set end of output to limit
set limit to limit - 1
end if
repeat with i from limit to 2 by -1
if (n mod i is 0) then
set beginning of output to i
set end of output to n div i
end if
end repeat
set beginning of output to 1
end if
return output
end properDivisors
-- Task code.
local output, astid, i, maxPDs, maxPDNums, pdCount
set output to {}
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ", "
repeat with i from 1 to 10
set end of output to (i as text) & "'s proper divisors: {" & properDivisors(i) & "}"
end repeat
set maxPDs to 0
set maxPDNums to {}
repeat with i from 1 to 20000
set pdCount to (count properDivisors(i))
if (pdCount > maxPDs) then
set maxPDs to pdCount
set maxPDNums to {i}
else if (pdCount = maxPDs) then
set end of maxPDNums to i
end if
end repeat
set end of output to linefeed & "Largest number of proper divisors for any number from 1 to 20,000: " & maxPDs
set end of output to "Numbers with this many: " & maxPDNums
set AppleScript's text item delimiters to linefeed
set output to output as text
set AppleScript's text item delimiters to astid
return output</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"1's proper divisors: {}
2's proper divisors: {1}
3's proper divisors: {1}
4's proper divisors: {1, 2}
5's proper divisors: {1}
6's proper divisors: {1, 2, 3}
7's proper divisors: {1}
8's proper divisors: {1, 2, 4}
9's proper divisors: {1, 3}
10's proper divisors: {1, 2, 5}
Largest number of proper divisors for any number from 1 to 20,000: 79
Numbers with this many: 15120, 18480"</syntaxhighlight>
=={{header|Arc}}==
<syntaxhighlight lang="arc">
;; Given num, return num and the list of its divisors
Line 672 ⟶ 884:
(div-lists 20000)
;; This took about 10 minutes on my machine.
</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="arc">
(1 0)
(2 1)
Line 695 ⟶ 907:
It is the number 18480.
There are 2 numbers with this trait, and they are (18480 15120)
</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program proFactor.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/*******************************************/
/* Constantes */
/*******************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
/*******************************************/
/* Initialized data */
/*******************************************/
.data
szMessStartPgm: .asciz "Program start \n"
szMessEndPgm: .asciz "Program normal end.\n"
szMessError: .asciz "\033[31mError Allocation !!!\n"
szCarriageReturn: .asciz "\n"
/* datas message display */
szMessEntete: .ascii "Number :"
sNumber: .space 12,' '
.asciz " Divisors :"
szMessResult: .ascii " "
sValue: .space 12,' '
.asciz ""
szMessDivNumber: .ascii "\nnumber divisors :"
sCounter: .space 12,' '
.asciz "\n"
szMessNumberMax: .ascii "Number :"
sNumberMax: .space 12,' '
.ascii " has "
sDivMax: .space 12, ' '
.asciz " divisors\n"
/*******************************************/
/* UnInitialized data */
/*******************************************/
.bss
/*******************************************/
/* code section */
/*******************************************/
.text
.global main
main: @ program start
ldr r0,iAdrszMessStartPgm @ display start message
bl affichageMess
mov r2,#1
1:
mov r0,r2 @ number
ldr r1,iAdrsNumber @ and convert ascii string
bl conversion10
ldr r0,iAdrszMessEntete @ display result message
bl affichageMess
mov r0,r2 @ number
mov r1,#1 @ display flag
bl divisors @ display divisors
ldr r1,iAdrsCounter @ and convert ascii string
bl conversion10
ldr r0,iAdrszMessDivNumber @ display result message
bl affichageMess
add r2,r2,#1
cmp r2,#10
ble 1b
mov r2,#2
mov r3,#0
mov r4,#0
ldr r5,iMaxi
2:
mov r0,r2
mov r1,#0 @ display flag
bl divisors @ display divisors
cmp r0,r3
movgt r3,r0
movgt r4,r2
add r2,r2,#1
cmp r2,r5
ble 2b
mov r0,r4
ldr r1,iAdrsNumberMax @ and convert ascii string
bl conversion10
mov r0,r3
ldr r1,iAdrsDivMax @ and convert ascii string
bl conversion10
ldr r0,iAdrszMessNumberMax
bl affichageMess
ldr r0,iAdrszMessEndPgm @ display end message
bl affichageMess
b 100f
99: @ display error message
ldr r0,iAdrszMessError
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc 0 @ perform system call
iAdrszMessStartPgm: .int szMessStartPgm
iAdrszMessEndPgm: .int szMessEndPgm
iAdrszMessError: .int szMessError
iAdrszCarriageReturn: .int szCarriageReturn
iAdrszMessResult: .int szMessResult
iAdrsValue: .int sValue
iAdrszMessDivNumber: .int szMessDivNumber
iAdrsCounter: .int sCounter
iAdrszMessEntete: .int szMessEntete
iAdrsNumber: .int sNumber
iAdrszMessNumberMax: .int szMessNumberMax
iAdrsDivMax: .int sDivMax
iAdrsNumberMax: .int sNumberMax
iMaxi: .int 20000
/******************************************************************/
/* divisors function */
/******************************************************************/
/* r0 contains the number */
/* r1 contains display flag (<>0: display, 0: no display )
/* r0 return divisors number */
divisors:
push {r1-r8,lr} @ save registers
cmp r0,#1 @ = 1 ?
movle r0,#0
ble 100f
mov r7,r0
mov r8,r1
cmp r8,#0
beq 1f
mov r0,#1 @ first divisor = 1
ldr r1,iAdrsValue @ and convert ascii string
bl conversion10
ldr r0,iAdrszMessResult @ display result message
bl affichageMess
1: @ begin loop
lsr r4,r7,#1 @ Maxi
mov r6,r4 @ first divisor
mov r5,#1 @ Counter divisors
2:
mov r0,r7 @ dividende = number
mov r1,r6 @ divisor
bl division
cmp r3,#0 @ remainder = 0 ?
bne 3f
add r5,r5,#1 @ increment counter
cmp r8,#0 @ display divisor ?
beq 3f
mov r0,r2 @ divisor
ldr r1,iAdrsValue @ and convert ascii string
bl conversion10
ldr r0,iAdrszMessResult @ display result message
bl affichageMess
3:
sub r6,r6,#1 @ decrement divisor
cmp r6,#2 @ End ?
bge 2b @ no loop
mov r0,r5 @ return divisors number
100:
pop {r1-r8,lr} @ restaur registers
bx lr @ return
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
{{Output}}
<pre>
Program start
Number :1 Divisors :
number divisors :0
Number :2 Divisors : 1 2
number divisors :2
Number :3 Divisors : 1 3
number divisors :2
Number :4 Divisors : 1 2
number divisors :2
Number :5 Divisors : 1
number divisors :1
Number :6 Divisors : 1 2 3
number divisors :3
Number :7 Divisors : 1
number divisors :1
Number :8 Divisors : 1 2 4
number divisors :3
Number :9 Divisors : 1 3
number divisors :2
Number :10 Divisors : 1 2 5
number divisors :3
Number :15120 has 79 divisors
Program normal end.
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">properDivisors: function [x] ->
(factors x) -- x
loop 1..10 'x ->
print ["proper divisors of" x "=>" properDivisors x]
maxN: 0
maxProperDivisors: 0
loop 1..20000 'x [
pd: size properDivisors x
if maxProperDivisors < pd [
maxN: x
maxProperDivisors: pd
]
]
print ["The number with the most proper divisors (" maxProperDivisors ") is" maxN]</syntaxhighlight>
{{out}}
<pre>proper divisors of 1 => []
proper divisors of 2 => [1]
proper divisors of 3 => [1]
proper divisors of 4 => [1 2]
proper divisors of 5 => [1]
proper divisors of 6 => [1 2 3]
proper divisors of 7 => [1]
proper divisors of 8 => [1 2 4]
proper divisors of 9 => [1 3]
proper divisors of 10 => [1 2 5]
The number with the most proper divisors ( 79 ) is 15120</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">proper_divisors(n) {
Array := []
if n = 1
return Array
Array[1] := true
x := Floor(Sqrt(n))
loop, % x+1
if !Mod(n, i:=A_Index+1) && (floor(n/i) < n)
Array[floor(n/i)] := true
Loop % n/x
if !Mod(n, i:=A_Index+1) && (i < n)
Array[i] := true
return Array
}</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">output := "Number`tDivisors`tCount`n"
loop, 10
{
output .= A_Index "`t"
for n, bool in x := proper_divisors(A_Index)
output .= n " "
output .= "`t" x.count() "`n"
}
maxDiv := 0, numDiv := []
loop, 20000
{
Arr := proper_divisors(A_Index)
numDiv[Arr.count()] := (numDiv[Arr.count()] ? numDiv[Arr.count()] ", " : "") A_Index
maxDiv := maxDiv > Arr.count() ? maxDiv : Arr.count()
}
output .= "`nNumber(s) in the range 1 to 20,000 with the most proper divisors:`n" numDiv.Pop() " with " maxDiv " divisors"
MsgBox % output
return</syntaxhighlight>
{{out}}
<pre>Number Divisors Count
1 0
2 1 1
3 1 1
4 1 2 2
5 1 1
6 1 2 3 3
7 1 1
8 1 2 4 3
9 1 3 2
10 1 2 5 3
Number(s) in the range 1 to 20,000 with the most proper divisors:
15120, 18480 with 79 divisors</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f PROPER_DIVISORS.AWK
BEGIN {
Line 735 ⟶ 1,230:
return
}
</syntaxhighlight>
<p>output:</p>
<pre>
Line 753 ⟶ 1,248:
18480 79 divisors not shown
</pre>
=={{header|BASIC}}==
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">FUNCTION CountProperDivisors (number)
IF number < 2 THEN CountProperDivisors = 0
count = 0
FOR i = 1 TO number \ 2
IF number MOD i = 0 THEN count = count + 1
NEXT i
CountProperDivisors = count
END FUNCTION
SUB ListProperDivisors (limit)
IF limit < 1 THEN EXIT SUB
FOR i = 1 TO limit
PRINT USING "## ->"; i;
IF i = 1 THEN PRINT " (None)";
FOR j = 1 TO i \ 2
IF i MOD j = 0 THEN PRINT " "; j;
NEXT j
PRINT
NEXT i
END SUB
most = 1
maxCount = 0
PRINT "The proper divisors of the following numbers are: "; CHR$(10)
ListProperDivisors (10)
FOR n = 2 TO 20000
'' It is extremely slow in this loop
count = CountProperDivisors(n)
IF count > maxCount THEN
maxCount = count
most = n
END IF
NEXT n
PRINT
PRINT most; " has the most proper divisors, namely "; maxCount
END</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC o PureBasic.
</pre>
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">subroutine ListProperDivisors(limit)
if limit < 1 then return
for i = 1 to limit
print i; " ->";
if i = 1 then
print " (None)"
continue for
end if
for j = 1 to i \ 2
if i mod j = 0 then print " "; j;
next j
print
next i
end subroutine
function CountProperDivisors(number)
if number < 2 then return 0
dim cont = 0
for i = 1 to number \ 2
if number mod i = 0 then cont += 1
next i
return cont
end function
most = 1
maxCount = 0
print "The proper divisors of the following numbers are:"
print
call ListProperDivisors(10)
for n = 2 to 20000
cont = CountProperDivisors(n)
if cont > maxCount then
maxCount = cont
most = n
end if
next n
print
print most; " has the most proper divisors, namely "; maxCount
end</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC o PureBasic.
</pre>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">let m = 1
let l = 10
if l >= 1 then
for i = 1 to l
if i = 1 then
print i, " : (None)"
else
for j = 1 to int(i / 2)
if i % j = 0 then
print i, " :", j
endif
next j
endif
next i
endif
for n = 2 to 20000
let c = 0
if n >= 2 then
for i = 1 to int(n / 2)
if n % i = 0 then
let c = c + 1
endif
next i
endif
if c > x then
let x = c
let m = n
endif
wait
next n
print m, " has the most proper divisors", comma, " namely ", x</syntaxhighlight>
{{out| Output}}<pre>
1 : (None)
2 : 1
3 : 1
4 : 1 2
5 : 1
6 : 1 2 3
7 : 1
8 : 1 2 4
9 : 1 3
10 : 1 2 5
15120 has the most proper divisors, namely 79
</pre>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION CountProperDivisors (number)
IF number < 2 THEN LET CountProperDivisors = 0
LET count = 0
FOR i = 1 TO INT(number / 2)
IF MOD(number, i) = 0 THEN LET count = count + 1
NEXT i
LET CountProperDivisors = count
END FUNCTION
SUB ListProperDivisors (limit)
IF limit < 1 THEN EXIT SUB
FOR i = 1 TO limit
PRINT i; " ->";
IF i = 1 THEN PRINT " (None)";
FOR j = 1 TO INT(i / 2)
IF MOD(i, j) = 0 THEN PRINT " "; j;
NEXT j
PRINT
NEXT i
END SUB
LET most = 1
LET maxCount = 0
PRINT "The proper divisors of the following numbers are: "; CHR$(10)
CALL LISTPROPERDIVISORS (10)
FOR n = 2 TO 20000
LET count = CountProperDivisors(n)
IF count > maxCount THEN
LET maxCount = count
LET most = n
END IF
NEXT n
PRINT
PRINT most; "has the most proper divisors, namely"; maxCount
END</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC o PureBasic.
</pre>
==={{header|Yabasic}}===
<syntaxhighlight lang="yabasic">sub ListProperDivisors(limit)
if limit < 1 then return : fi
for i = 1 to limit
print i, " ->";
if i = 1 then
print " (None)"
continue //for
endif
for j = 1 to int(i / 2)
if mod(i, j) = 0 then print " ", j; : fi
next j
print
next i
end sub
sub CountProperDivisors(number)
if number < 2 then return 0 : fi
count = 0
for i = 1 to int(number / 2)
if mod(number, i) = 0 then count = count + 1 : fi
next i
return count
end sub
most = 1
maxCount = 0
print "The proper divisors of the following numbers are: \n"
ListProperDivisors(10)
for n = 2 to 20000
count = CountProperDivisors(n)
if count > maxCount then
maxCount = count
most = n
endif
next n
print
print most, " has the most proper divisors, namely ", maxCount
end</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC o PureBasic.
</pre>
=={{header|BaCon}}==
<
FUNCTION ProperDivisor(nr, show)
Line 786 ⟶ 1,542:
PRINT "Most proper divisors for number in the range 1-20000: ", MagicNumber, " with ", MaxDivisors, " divisors."
</syntaxhighlight>
{{out}}
<pre>
Line 805 ⟶ 1,561:
===Brute Force===
C has tedious boilerplate related to allocating memory for dynamic arrays, so we just skip the problem of storing values altogether.
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdbool.h>
Line 848 ⟶ 1,604:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 865 ⟶ 1,621:
===Number Theoretic===
There is no need to go through all the divisors if only the count is needed, this implementation refines the brute force approach by solving the second part of the task via a Number Theory formula. The running time is noticeably faster than the brute force method above. Output is same as the above.
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdbool.h>
Line 935 ⟶ 1,691:
return 0;
}
</syntaxhighlight>
=={{header|C sharp}}==
<
{
using System;
Line 969 ⟶ 1,725:
}
}
}</
{{out}}
<pre>1: {}
Line 982 ⟶ 1,738:
10: {1, 2, 5}
15120: 79</pre>
=={{header|C++}}==
<
#include <iostream>
#include <algorithm>
Line 1,021 ⟶ 1,778:
return 0 ;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,048 ⟶ 1,805:
=={{header|Ceylon}}==
<
function divisors(Integer int) =>
Line 1,069 ⟶ 1,826:
print("the number(s) with the most divisors between ``start`` and ``end`` is/are:
``mostDivisors?.item else "nothing"`` with ``mostDivisors?.key else "no"`` divisors");
}</
{{out}}
<pre>1 => []
Line 1,085 ⟶ 1,842:
=={{header|Clojure}}==
<
(:gen-class))
Line 1,120 ⟶ 1,877:
(println n " has " (count factors) " divisors"))
</syntaxhighlight>
{{Output}}
<pre>
Line 1,137 ⟶ 1,894:
18480 has 79 divisors
</pre>
=={{header|Common Lisp}}==
Ideally, the smallest-divisor function would only try prime numbers instead of odd numbers.
<
"(int,list)->list::Function to find all proper divisors of a +ve integer."
Line 1,174 ⟶ 1,932:
(dotimes (i 10) (format t "~A:~A~%" (1+ i) (proper-divisors-recursive (1+ i))))
(format t "Task 2:Count & list of numbers <=20,000 with the most Proper Divisors:~%~A~%"
(task #'proper-divisors-recursive)))</
{{out}}
<pre>CL-USER(10): (main)
Line 1,194 ⟶ 1,952:
=={{header|Component Pascal}}==
{{Works with|Black Box Component Builder}}
<
MODULE RosettaProperDivisor;
IMPORT StdLog;
Line 1,250 ⟶ 2,008:
^Q RosettaProperDivisor.Do~
</syntaxhighlight>
{{out}}
<pre>
Line 1,267 ⟶ 2,025:
18480
</pre>
=={{header|D}}==
{{trans|Python}}
Currently the lambda of the filter allocates a closure on the GC-managed heap.
<
import std.stdio, std.algorithm, std.range, std.typecons;
Line 1,278 ⟶ 2,037:
iota(1, 11).map!properDivs.writeln;
iota(1, 20_001).map!(n => tuple(properDivs(n).count, n)).reduce!max.writeln;
}</
{{out}}
<pre>[[], [1], [1], [1, 2], [1], [1, 2, 3], [1], [1, 2, 4], [1, 3], [1, 2, 5]]
Tuple!(uint, int)(79, 18480)</pre>
The Run-time is about 0.67 seconds with the ldc2 compiler.
=={{header|Delphi}}==
{{trans|C#}}
<syntaxhighlight lang="delphi">
program ProperDivisors;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils,
System.Generics.Collections;
type
TProperDivisors = TArray<Integer>;
function GetProperDivisors(const value: Integer): TProperDivisors;
var
i, count: Integer;
begin
count := 0;
for i := 1 to value div 2 do
begin
if value mod i = 0 then
begin
inc(count);
SetLength(result, count);
Result[count - 1] := i;
end;
end;
end;
procedure Println(values: TProperDivisors);
var
i: Integer;
begin
Write('[');
if Length(values) > 0 then
for i := 0 to High(values) do
Write(Format('%2d', [values[i]]));
Writeln(']');
end;
var
number, max_count, count, max_number: Integer;
begin
for number := 1 to 10 do
begin
write(number, ': ');
Println(GetProperDivisors(number));
end;
max_count := 0;
for number := 1 to 20000 do
begin
count := length(GetProperDivisors(number));
if count > max_count then
begin
max_count := count;
max_number := number;
end;
end;
Write(max_number, ': ', max_count);
readln;
end.
</syntaxhighlight>
{{out}}
<pre>
1: []
2: [ 1]
3: [ 1]
4: [ 1 2]
5: [ 1]
6: [ 1 2 3]
7: [ 1]
8: [ 1 2 4]
9: [ 1 3]
10: [ 1 2 5]
15120: 79
</pre>
Version with TParallel.For
<syntaxhighlight lang="delphi">
program ProperDivisors;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils,
System.Threading,
System.SyncObjs;
type
TProperDivisors = array of Integer;
function GetProperDivisors(const value: Integer): TProperDivisors;
var
i, count: Integer;
begin
count := 0;
for i := 1 to value div 2 do
begin
if value mod i = 0 then
begin
inc(count);
SetLength(result, count);
Result[count - 1] := i;
end;
end;
end;
procedure Println(values: TProperDivisors);
var
i: Integer;
begin
Write('[');
if Length(values) > 0 then
for i := 0 to High(values) do
Write(Format('%2d', [values[i]]));
Writeln(']');
end;
var
number, max_count, count, max_number: Integer;
begin
for number := 1 to 10 do
begin
write(number, ': ');
Println(GetProperDivisors(number));
end;
max_count := 0;
TParallel.for (1, 20000,
procedure(I: Int64)
begin
count := length(GetProperDivisors(I));
if count > max_count then
begin
TInterlocked.Exchange(max_count, count);
TInterlocked.Exchange(max_number, I);
end;
end);
Writeln(max_number, ': ', max_count);
readln;
end.
</syntaxhighlight>
=={{header|Dyalect}}==
Line 1,288 ⟶ 2,203:
{{trans|Swift}}
<
if n == 1 {
}
for x in 1..
if n % x == 0 {
yield x
Line 1,298 ⟶ 2,213:
}
}
for i in 1..10 {
print("\(i): \(properDivs(i).
}
Line 1,306 ⟶ 2,221:
for i in 1..20000 {
if count > max {
set (num, max) = (i, count)
Line 1,312 ⟶ 2,227:
}
print("\(num): \(max)")</
{{out}}
Line 1,327 ⟶ 2,242:
10: [1, 2, 5]
15120: 79</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
proc propdivs n . divs[] .
divs[] = [ ]
if n < 2
return
.
divs[] &= 1
sqr = sqrt n
for d = 2 to sqr
if n mod d = 0
divs[] &= d
if d <> sqr
divs[] &= n / d
.
.
.
.
for i to 10
propdivs i d[]
write i & ":"
print d[]
.
for i to 20000
propdivs i d[]
if len d[] > max
max = len d[]
maxi = i
.
.
print maxi & " has " & max & " proper divisors."
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(lib 'list) ;; list-delete
Line 1,373 ⟶ 2,321:
</syntaxhighlight>
{{out}}
<
(for ((i (in-range 1 11))) (writeln i (divs i)))
1 null
Line 1,396 ⟶ 2,344:
(lib 'bigint)
(numdivs 95952222101012742144) → 666 ;; 🎩
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,452 ⟶ 2,400:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,470 ⟶ 2,418:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def divisors(1), do: []
def divisors(n), do: [1 | divisors(2,n,:math.sqrt(n))] |> Enum.sort
Line 1,489 ⟶ 2,437:
IO.puts "#{n}: #{inspect Proper.divisors(n)}"
end)
Proper.most_divisors(20000)</
{{out}}
Line 1,506 ⟶ 2,454:
</pre>
=={{
<
-export([divs/1,sumdivs/1,longest/1]).
Line 1,534 ⟶ 2,482:
longest(L,Acc,A,Acc+1);
true -> longest(L,Current,CurLeng,Acc+1)
end.</
{{out}}
<pre>
Line 1,554 ⟶ 2,502:
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// the simple function with the answer
let propDivs n = [1..n/2] |> List.filter (fun x->n % x = 0)
Line 1,609 ⟶ 2,523:
|> Seq.fold (fun a b ->match a,b with | (_,c1,_),(_,c2,_) when c2 > c1 -> b | _-> a) (0,0,[])
|> fun (n,count,_) -> (n,count,[]) |> show
</syntaxhighlight>
{{out}}
Line 1,627 ⟶ 2,541:
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: formatting io kernel math math.functions
: #divisors ( m -- n )
dup sqrt >integer 1 + [1,b] [ divisor? ] with count dup +
1 - ;
10 [1,b] [ dup pprint bl divisors but-last . ] each
20000 [1,b] [ #divisors ] supremum-by dup #divisors
"%d with %d divisors.\n" printf</syntaxhighlight>
{{out}}
Line 1,648 ⟶ 2,566:
15120 with 79 divisors.
</pre>
=={{header|Fermat}}==
<syntaxhighlight lang="fermat">Func Divisors(n) =
[d]:=[(1)]; {start divisor list with just 1, which is a divisor of everything}
for i = 2 to n\2 do {loop through possible divisors of n}
if Divides(i, n) then [d]:=[d]_[(i)] fi
od;
.;
for n = 1 to 10 do
Divisors(n);
!!(n,' ',[d);
od;
record:=0;
champ:=1;
for n=2 to 20000 do
Divisors(n);
m:=Cols[d]; {this gets the length of the array}
if m > record then
champ:=n;
record:=m;
fi;
od;
!!('The number up to 20,000 with the most divisors was ',champ,' with ',record,' divisors.');</syntaxhighlight>
{{out}}<pre>
1 1
2 1
3 1
4 1, 2
5 1
6 1, 2, 3
7 1
8 1, 2, 4
9 1, 3
10 1, 2, 5
The number up to 20,000 with the most divisors was 15120 with 79 divisors.</pre>
=={{header|Forth}}==
{{works with|gforth|0.7.3}}
<syntaxhighlight lang="forth">: .proper-divisors
dup 1 ?do
dup i mod 0= if i . then
loop cr drop
;
: proper-divisors-count
0 swap
dup 1 ?do
dup i mod 0= if swap 1 + swap then
loop drop
;
: rosetta-proper-divisors
cr
11 1 do
i . ." : " i .proper-divisors
loop
1 0
20000 2 do
i proper-divisors-count
2dup < if nip nip i swap else drop then
loop
swap cr . ." has " . ." divisors" cr
;
rosetta-proper-divisors</syntaxhighlight>
{{out}}
<pre>1 :
2 : 1
3 : 1
4 : 1 2
5 : 1
6 : 1 2 3
7 : 1
8 : 1 2 4
9 : 1 3
10 : 1 2 5
15120 has 79 divisors
ok</pre>
=={{header|Fortran}}==
Compiled using G95 compiler, run on x86 system under Puppy Linux
<syntaxhighlight lang="fortran">
function icntprop(num )
Line 1,682 ⟶ 2,689:
print *,maxj,' has max proper divisors: ',maxcnt
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,720 ⟶ 2,727:
=={{header|FreeBASIC}}==
<
' FreeBASIC v1.05.0 win64
Line 1,768 ⟶ 2,775:
Sleep
End
</syntaxhighlight>
{{out}}
Line 1,786 ⟶ 2,793:
15120 has the most proper divisors, namely 79
</pre>
=={{header|Frink}}==
Frink's built-in factorization routines efficiently find factors of arbitrary-sized integers.
<syntaxhighlight lang="frink">
for n = 1 to 10
println["$n\t" + join[" ", properDivisors[n]]]
println[]
d = new dict
for n = 1 to 20000
{
c = length[properDivisors[n]]
d.addToList[c, n]
}
most = max[keys[d]]
println[d@most + " have $most factors"]
properDivisors[n] := allFactors[n, true, false, true]
</syntaxhighlight>
{{out}}
<pre>
1
2 1
3 1
4 1 2
5 1
6 1 2 3
7 1
8 1 2 4
9 1 3
10 1 2 5
[15120, 18480] have 79 factors
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn ProperDivisors( n as long ) as CFArrayRef
CFMutableArrayRef array = fn MutableArrayWithCapacity(0)
if ( n < 2 ) then exit fn
long i
for i = 1 to n - 1
if ( n mod i == 0 )
MutableArrayAddObject( array, @(i) )
end if
next
end fn = array
void local fn DoIt
long n, count, num, max = 0
for n = 1 to 10
printf @"%2ld: %@",n,fn ArrayComponentsJoinedByString( fn ProperDivisors( n ), @" " )
next
for n = 1 to 20000
count = len( fn Properdivisors( n ) )
if ( count > max )
max = count
num = n
end if
next
print: print num;@" has the most proper divisors with ";max
end fn
fn DoIt
HandleEvents
</syntaxhighlight>
{{out}}
<pre>
1:
2: 1
3: 1
4: 1 2
5: 1
6: 1 2 3
7: 1
8: 1 2 4
9: 1 3
10: 1 2 5
15120 has the most proper divisors with 79
</pre>
=={{header|GFA Basic}}==
<syntaxhighlight lang="text">
OPENW 1
CLEARW 1
Line 1,866 ⟶ 2,964:
RETURN count%-1
ENDFUNC
</syntaxhighlight>
Output is:
Line 1,885 ⟶ 2,983:
=={{header|Go}}==
{{trans|Kotlin}}
<
import (
Line 1,946 ⟶ 3,044:
fmt.Println(n)
}
}</
{{out}}
Line 1,970 ⟶ 3,068:
=={{header|Haskell}}==
<
import Data.List
Line 1,982 ⟶ 3,080:
putStrLn "a number with the most divisors within 1 to 20000 (number, count):"
print $ maximumBy (comparing snd)
[(n, length $ divisors n) | n <- [1 .. 20000]]</
{{out}}
<pre>divisors of 1 to 10:
Line 1,998 ⟶ 3,096:
(18480,79)</pre>
<
import Data.Ord (comparing)
import
properDivisors
Line 2,010 ⟶ 3,108:
let root = (floor . sqrt . fromIntegral) n
lows = filter ((0 ==) . rem n) [1 .. root]
in init (lows ++ bool id tail (n == root * root) (reverse (quot n <$> lows)))
main :: IO ()
Line 2,030 ⟶ 3,123:
print $
maximumBy (comparing snd) $
{{Out}}
<pre>Proper divisors of 1 to 10:
Line 2,043 ⟶ 3,136:
[1,3]
[1,2,5]
A number in the range 1 to 20,000 with the most proper divisors,
as (number, count of proper divisors):
(18480,79)</pre>
and we can also define properDivisors in terms of primeFactors:
<syntaxhighlight lang="haskell">import Data.Numbers.Primes (primeFactors)
import Data.List (group, maximumBy, sort)
import Data.Ord (comparing)
properDivisors :: Int -> [Int]
properDivisors =
init . sort . foldr (
flip ((<*>) . fmap (*)) . scanl (*) 1
) [1] . group . primeFactors
---------------------------TEST----------------------------
main :: IO ()
main = do
putStrLn $
fTable "Proper divisors of [1..10]:" show show properDivisors [1 .. 10]
mapM_
putStrLn
[ ""
, "A number in the range 1 to 20,000 with the most proper divisors,"
, "as (number, count of proper divisors):"
, ""
]
print $
maximumBy (comparing snd) $
(,) <*> (length . properDivisors) <$> [1 .. 20000]
--------------------------DISPLAY--------------------------
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String
fTable s xShow fxShow f xs =
let rjust n c = (drop . length) <*> (replicate n c ++)
w = maximum (length . xShow <$> xs)
in unlines $
s : fmap (((++) . rjust w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs</syntaxhighlight>
{{Out}}
<pre>Proper divisors of [1..10]:
1 -> []
2 -> [1]
3 -> [1]
4 -> [1,2]
5 -> [1]
6 -> [1,2,3]
7 -> [1]
8 -> [1,2,4]
9 -> [1,3]
10 -> [1,2,5]
A number in the range 1 to 20,000 with the most proper divisors,
Line 2,055 ⟶ 3,202:
So, borrowing from [[Factors of an integer#J|the J implementation]] of that related task:
<
properDivisors=: factors -. ]</
Proper divisors of numbers 1 through 10:
<
1 --
2 -- 1
Line 2,070 ⟶ 3,217:
8 -- 1 2 4
9 -- 1 3
10 -- 1 2 5</
Number(s) not exceeding 20000 with largest number of proper divisors (and the count of those divisors):
<
15120 79
18480 79</
Note that it's a bit more efficient to simply count factors here, when selecting the candidate numbers.
<
15120 79
18480 79</
We could also arbitrarily toss either 15120 or 18480 (keeping the other number), if it were important that we produce only one result.
Line 2,088 ⟶ 3,235:
=={{header|Java}}==
{{works with|Java|1.5+}}
<
import java.util.LinkedList;
import java.util.List;
Line 2,120 ⟶ 3,267:
System.out.println(x + ": " + count);
}
}</
{{out}}
<pre>1: []
Line 2,138 ⟶ 3,285:
===ES5===
<
// Proper divisors
Line 2,206 ⟶ 3,353:
);
})();</
{{out}}
Line 2,241 ⟶ 3,388:
===ES6===
<
'use strict';
// properDivisors :: Int -> [Int]
// The integer divisors
const
intRoot = Math.floor(rRoot),
blnPerfectSquare = rRoot === intRoot,
lows = enumFromTo(1)(intRoot)
.filter(x => 0 === (n % x));
// For perfect squares, we can
// the head of the 'highs'
return lows.concat(lows
.map(x => n / x)
.reverse()
.slice(blnPerfectSquare | 0)
)
.slice(0, -1); // except n itself
};
// ------------------------TESTS-----------------------
// main :: IO ()
const main =
fTable('Proper divisors of
JSON.stringify
)(properDivisors)(enumFromTo(1)(10)),
'',
'Example of maximum divisor count in the range [1..20000]:',
' ' + maximumBy(comparing(snd))(
enumFromTo(1)(20000).map(
n => [n, properDivisors(n).length]
)
// -----------------GENERIC FUNCTIONS------------------
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
x => y => {
const
a = f(x),
b = f(y);
return a < b ? -1 : (a > b ? 1 : 0);
};
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = m => n =>
length: 1 + n
}, (_, i) => m +
// fTable :: String -> (a -> String) -> (b -> String)
//
const fTable = s => xShow => fxShow => f =>
// Heading -> x display function
// fx display function ->
// f -> values -> tabular string
const
ys = xs.map(xShow),
w = Math.max(...ys.map(x => x.length));
return s + '\n' + zipWith(
a => b => a.padStart(w, ' ') + ' -> ' + b
)(ys)(
xs.map(x => fxShow(f(x)))
).join('\n');
};
// maximumBy :: (a -> a -> Ordering)
const maximumBy = f => xs
0 < xs.length ?
.reduce((a, x) => 0 < f(x)(a) ? x : a, xs[0])
) : undefined;
// snd :: (a, b) ->
const snd = tpl =>
// str :: a -> String
const str = x => x.toString();
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = p => f => x => {
let v = x;
while (!p(v)) v = f(v);
return v;
};
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f => xs => ys => {
const
lng = Math.min(xs.length, xs.length),
as = xs.slice(0, lng),
bs = ys.slice(0, lng);
return Array.from({
length: lng
}, (_, i) => f(as[i])(
bs[i]
));
};
// MAIN ---
return main();
})();</syntaxhighlight>
{{Out}}
<pre>Proper divisors of [1..10]:
1 -> []
2 -> [1]
3 -> [1]
4 ->
5 -> [1]
6 -> [1,2,3]
7 -> [1]
8 -> [1,2,4]
9 -> [1,3]
10 -> [1,2,5]
Example of maximum divisor count in the range [1..20000]:
15120 has 79 proper divisors.</pre>
=={{header|jq}}==
{{works with|jq|1.4}}
In the following, proper_divisors returns a stream. In order to count the number of items in the stream economically, we first define "count(stream)":
<
# unordered
Line 2,327 ⟶ 3,537:
( [null, 0];
count( $i | proper_divisors ) as $count
| if $count > .[1] then [$i, $count] else . end);</
'''The tasks:'''
<
(range(1;11) as $i | "\($i): \( [ $i | proper_divisors] )"),
"",
Line 2,335 ⟶ 3,545:
"the maximal number proper divisors together with the corresponding",
"count of proper divisors is:",
most_proper_divisors(20000) </
{{out}}
<
The proper divisors of the numbers 1 to 10 inclusive are:
1: []
Line 2,353 ⟶ 3,563:
the maximal number proper divisors together with the corresponding
count of proper divisors is:
[15120,79]</
=={{header|Julia}}==
Use <code>factor</code> to obtain the prime factorization of the target number. I adopted the argument handling style of <code>factor</code> in my <code>properdivisors</code> function.
<syntaxhighlight lang="julia">
using Primes
function properdivisors(n::T) where {T<:Integer}
0 < n || throw(ArgumentError("number to be factored must be ≥ 0, got $n"))
1 < n || return T[]
!isprime(n) || return T[one(T)
f = factor(n)
d = T[one(T)]
Line 2,397 ⟶ 3,608:
println(nlst, " have the maximum proper divisor count of ", maxdiv, ".")
</syntaxhighlight>
{{out}}
Line 2,418 ⟶ 3,629:
=={{header|Kotlin}}==
<
fun listProperDivisors(limit: Int) {
Line 2,457 ⟶ 3,668:
println("The following number(s) have the most proper divisors, namely " + maxCount + "\n")
for (n in most) println(n)
}</
{{out}}
Line 2,478 ⟶ 3,689:
15120
18480
</pre>
=={{header|langur}}==
{{trans|Go}}
<syntaxhighlight lang="langur">val .getproper = fn .x: for[=[]] .i of .x \ 2 { if .x div .i: _for ~= [.i] }
val .cntproper = fn .x: for[=0] .i of .x \ 2 { if .x div .i: _for += 1 }
val .listproper = fn(.x) {
if .x < 1: return null
for[=""] .i of .x {
_for ~= "{{.i:2}} -> {{.getproper(.i)}}\n"
}
}
writeln "The proper divisors of the following numbers are :"
writeln .listproper(10)
var .max = 0
var .most = []
for .n in 2 .. 20_000 {
val .cnt = .cntproper(.n)
if .cnt == .max {
.most = more .most, .n
} else if .cnt > .max {
.max, .most = .cnt, [.n]
}
}
writeln "The following number(s) <= 20000 have the most proper divisors ({{.max}})"
writeln .most
</syntaxhighlight>
{{out}}
<pre>The proper divisors of the following numbers are :
1 -> []
2 -> [1]
3 -> [1]
4 -> [1, 2]
5 -> [1]
6 -> [1, 2, 3]
7 -> [1]
8 -> [1, 2, 4]
9 -> [1, 3]
10 -> [1, 2, 5]
The following number(s) <= 20000 have the most proper divisors (79)
[15120, 18480]
</pre>
=={{header|Lua}}==
<
function propDivs (n)
if n < 2 then return {} end
Line 2,512 ⟶ 3,771:
end
end
print(answer .. " has " .. mostDivs .. " proper divisors.")</
{{out}}
<pre>1:
Line 2,529 ⟶ 3,788:
A Function that yields the proper divisors of an integer n:
<
Proper divisors of n from 1 to 10:
<
{{out}}
<pre>1 {}
Line 2,546 ⟶ 3,805:
The number with the most divisors between 1 and 20,000:
<syntaxhighlight lang="mathematica">Fold[
Last[SortBy[{#1, {#2, Length@ProperDivisors[#2]}}, Last]] &,
{0, 0},
Range[20000]]</
{{out}}
<pre>{18480, 79}</pre>
An alternate way to find the number with the most divisors between 1 and 20,000:
<
Table[
{n, Length@ProperDivisors[n]},
{n, 1, 20000}],
Last]</
{{out}}
<pre>{15120, 79}</pre>
=={{header|
<syntaxhighlight lang="matlab">function D=pd(N)
K=1:ceil(N/2);
D=K(~(rem(N, K)));</syntaxhighlight>
{{out}}
<pre>
for I=1:10
Line 2,603 ⟶ 3,862:
79
</pre>
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 2,657 ⟶ 3,917:
ReadChar
END ProperDivisors.</
=={{header|
{{trans|C}}
<syntaxhighlight lang="nim">import strformat
proc properDivisors(n: int) =
var count = 0
for i in 1..<n:
if n
write(stdout, fmt"{i} ")
write(stdout, "\n")
proc countProperDivisors(n: int): int =
var nn = n
var prod =
var
while nn mod 2
nn = nn div 2
prod *= (1 +
while nn mod i
if nn >
prod - 1
for i in 1..10:
write(stdout, fmt"{i:2}: ")
properDivisors(i)
var max = 0
var maxI = 1
for i in 1..20000:
var v = countProperDivisors(i)
if v >= max:
max = v
maxI = i
echo fmt"{maxI} with {max} divisors"</syntaxhighlight>
{{out}}
<pre>
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
18480 with 79 divisors
</pre>
=={{header|Oberon-2}}==
<
MODULE ProperDivisors;
IMPORT
Line 2,818 ⟶ 4,076:
END
END ProperDivisors.
</syntaxhighlight>
{{out}}
<pre>
Line 2,835 ⟶ 4,093:
15120
18480
</pre>
=={{header|Objeck}}==
<syntaxhighlight lang="objeck">use Collection;
class Proper{
function : Main(args : String[]) ~ Nil {
for(x := 1; x <= 10; x++;) {
Print(x, ProperDivs(x));
};
x := 0;
count := 0;
for(n := 1; n <= 20000; n++;) {
if(ProperDivs(n)->Size() > count) {
x := n;
count := ProperDivs(n)->Size();
};
};
"{$x}: {$count}"->PrintLine();
}
function : ProperDivs(n : Int) ~ IntVector {
divs := IntVector->New();
if(n = 1) {
return divs;
};
divs->AddBack(1);
for(x := 2; x < n; x++;) {
if(n % x = 0) {
divs->AddBack(x);
};
};
divs->Sort();
return divs;
}
function : Print(x : Int, result : IntVector) ~ Nil {
"{$x}: "->Print();
result->ToArray()->ToString()->PrintLine();
}
}
</syntaxhighlight>
Output:
<pre>
1: []
2: [1]
3: [1]
4: [1,2]
5: [1]
6: [1,2,3]
7: [1]
8: [1,2,4]
9: [1,3]
10: [1,2,5]
15120: 79
</pre>
=={{header|Oforth}}==
<
10 seq apply(#[ dup print " : " print properDivs println ])
20000 seq map(#[ dup properDivs size Pair new ]) reduce(#maxKey) println</
{{out}}
<pre>
Line 2,859 ⟶ 4,178:
=={{header|PARI/GP}}==
<
apply(proper, [1..10])
r=at=0; for(n=1,20000, t=numdiv(n); if(t>r, r=t; at=n)); [at, numdiv(t)-1]</
{{out}}
<pre>%1 = [[], [2], [3], [2, 4], [5], [2, 3, 6], [7], [2, 4, 8], [3, 9], [2, 5, 10]]
Line 2,869 ⟶ 4,188:
{{works with|Free Pascal}}
Using prime factorisation
<
uses
sysutils;
Line 3,088 ⟶ 4,407:
j := CntProperDivs(primeDecomp);
PrimeFacOut(primeDecomp);writeln(' ',j:10,' factors'); writeln;
END.</
1 :
2 : 1
Line 3,109 ⟶ 4,428:
===Using a module for divisors===
{{libheader|ntheory}}
<
sub proper_divisors {
my $n = shift;
Line 3,131 ⟶ 4,450:
no warnings 'numeric';
say max(map { scalar(proper_divisors($_)) . " $_" } 1..20000);
}</
{{out}}
<pre>1:
Line 3,147 ⟶ 4,466:
Note that the first code will choose the first max, while the second chooses the last.
=={{header|Phix}}==
The factors routine is an auto-include. The actual implementation of it, from builtins\pfactors.e is
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">include1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- returns a list of all integer factors of n
-- if include1 is
-- if include1 is 1 the result contains 1 and n
-- if include1 is -1 the result contains 1 but not n
-- </span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">check_limits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"factors"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">hfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">hfactor</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">include1</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">include1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">hfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">lim</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lfactors</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">hfactor</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">p</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">hfactor</span><span style="color: #0000FF;">=</span><span style="color: #000000;">p</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">hfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hfactors</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hfactor</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">hfactors</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</syntaxhighlight>-->
The compiler knows where to find that, so the main program is just:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">candidates</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20000</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">maxd</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxd</span> <span style="color: #008080;">then</span>
<span style="color:
<span style="color:
<span style="color: #000000;">candidates</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">maxd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d divisors: %v\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">maxd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">candidates</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
0: {
4: {
8: {
10: {1,2,5}
79 divisors: {15120,18480}
</pre>
=={{header|PHP}}==
<
function ProperDivisors($n) {
yield 1;
Line 3,290 ⟶ 4,577:
echo "They have ", key($divisorsCount), " divisors.\n";
</syntaxhighlight>
Outputs:
Line 3,306 ⟶ 4,593:
Numbers with most divisors: 15120, 18480.
They have 79 divisors.</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">go =>
println(11111=proper_divisors(11111)),
nl,
foreach(N in 1..10)
println(N=proper_divisors(N))
end,
nl,
find_most_divisors(20_000),
nl.
% Proper divisors of number N
proper_divisors(N) = Divisors =>
Div1 = [ I : I in 1..ceiling(sqrt(N)), N mod I == 0],
Divisors = (Div1 ++ [N div I : I in Div1]).sort_remove_dups().delete(N).
% Find the number(s) with the most proper divisors below Limit
find_most_divisors(Limit) =>
MaxN = [],
MaxNumDivisors = [],
MaxLen = 1,
foreach(N in 1..Limit, not prime(N))
D = proper_divisors(N),
Len = D.len,
% Get all numbers with most proper divisors
if Len = MaxLen then
MaxN := MaxN ++ [N],
MaxNumDivisors := MaxNumDivisors ++ [[N=D]]
elseif Len > MaxLen then
MaxLen := Len,
MaxN := [N],
MaxNumDivisors := [N=D]
end
end,
println(maxN=MaxN),
println(maxLen=MaxLen),
nl.</syntaxhighlight>
{{out}}
<pre>11111 = [1,41,271]
1 = []
2 = [1]
3 = [1]
4 = [1,2]
5 = [1]
6 = [1,2,3]
7 = [1]
8 = [1,2,4]
9 = [1,3]
10 = [1,2,5]
maxN = [15120,18480]
maxLen = 79</pre>
===Larger tests===
Some larger tests of most number of divisors:
<syntaxhighlight lang="picat">go2 =>
time(find_most_divisors(100_000)),
nl,
time(find_most_divisors(1_000_000)),
nl.</syntaxhighlight>
{{out}}
<pre>maxN = [83160,98280]
maxLen = 127
maxN = [720720,831600,942480,982800,997920]
maxLen = 239</pre>
=={{header|PicoLisp}}==
<
(de propdiv (N)
(head -1 (filter
Line 3,317 ⟶ 4,678:
(mapcar propdiv (range 1 10))
# Output:
# (NIL (1) (1) (1 2) (1) (1 2 3) (1) (1 2 4) (1 3) (1 2 5))</
===Brute-force===
<
(cdr
(rot
Line 3,339 ⟶ 4,700:
(maxi
countdiv
(range 1 20000) ) )</
===Factorization===
<
(if (assoc Key (val Var))
(con @ (inc (cdr @)))
Line 3,364 ⟶ 4,725:
factor
(range 1 20000) )
@@ ) )</
Output:
<pre>
Line 3,372 ⟶ 4,733:
=={{header|PL/I}}==
<
(subrg):
cpd: Proc Options(main);
Line 3,435 ⟶ 4,796:
End;
End;</
{{out}}
<pre>
Line 3,455 ⟶ 4,816:
=={{header|PowerShell}}==
===version 1===
<syntaxhighlight lang="powershell">
function proper-divisor ($n) {
if($n -ge 2) {
Line 3,473 ⟶ 4,834:
"$(proper-divisor 496)"
"$(proper-divisor 2048)"
</syntaxhighlight>
===version 2===
<syntaxhighlight lang="powershell">
function proper-divisor ($n) {
if($n -ge 2) {
Line 3,492 ⟶ 4,853:
"$(proper-divisor 496)"
"$(proper-divisor 2048)"
</syntaxhighlight>
===version 3===
<syntaxhighlight lang="powershell">
function eratosthenes ($n) {
if($n -gt 1){
Line 3,545 ⟶ 4,906:
"$(proper-divisor 496)"
"$(proper-divisor 2048)"
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 3,559 ⟶ 4,920:
Taking a cue from [http://stackoverflow.com/a/171779 an SO answer]:
<
UpperBound is round(sqrt(N)),
between(1, UpperBound, D),
Line 3,606 ⟶ 4,967:
proper_divisor_count(N, Count) ),
max(MaxCount, Num) ),
Result = (num(Num)-divisor_count(MaxCount)).</
Output:
<
2:[1]
3:[1]
Line 3,624 ⟶ 4,985:
?- find_most_proper_divisors_in_range(1,20000,Result).
Result = num(15120)-divisor_count(79).
</syntaxhighlight>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">
EnableExplicit
Line 3,684 ⟶ 5,045:
CloseConsole()
EndIf
</syntaxhighlight>
{{out}}
Line 3,707 ⟶ 5,068:
===Python: Literal===
A very literal interpretation
<
... return {x for x in range(1, (n + 1) // 2 + 1) if n % x == 0 and n != x}
...
Line 3,718 ⟶ 5,079:
>>> length
79
>>> </
Line 3,736 ⟶ 5,097:
This version is over an order of magnitude faster for generating the proper divisors of the first 20,000 integers; at the expense of simplicity.
<
from functools import lru_cache, reduce
from collections import Counter
Line 3,780 ⟶ 5,141:
print([proper_divs(n) for n in range(1, 11)])
print(*max(((n, len(proper_divs(n))) for n in range(1, 20001)), key=lambda pd: pd[1]))</
{{out}}
Line 3,786 ⟶ 5,147:
15120 79</pre>
===Python: Functional===
Defining a list of proper divisors in terms of the prime factorization:
{{Works with|Python|3.7}}
<syntaxhighlight lang="python">'''Proper divisors'''
from itertools import accumulate, chain, groupby, product
from functools import reduce
from math import floor, sqrt
from operator import mul
# properDivisors :: Int -> [Int]
def properDivisors(n):
'''The ordered divisors of n, excluding n itself.
'''
def go(a, group):
return [x * y for x, y in product(
a,
accumulate(chain([1], group), mul)
)]
return sorted(
reduce(go, [
list(g) for _, g in groupby(primeFactors(n))
], [1])
)[:-1] if 1 < n else []
# --------------------------TEST---------------------------
# main :: IO ()
def main():
'''Tests'''
print(
fTable('Proper divisors of [1..10]:')(str)(str)(
properDivisors
)(range(1, 1 + 10))
)
print('\nExample of maximum divisor count in the range [1..20000]:')
print(
max(
[(n, len(properDivisors(n))) for n in range(1, 1 + 20000)],
key=snd
)
)
# -------------------------DISPLAY-------------------------
# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
'''
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# -------------------------GENERIC-------------------------
# primeFactors :: Int -> [Int]
def primeFactors(n):
'''A list of the prime factors of n.
'''
def f(qr):
r = qr[1]
return step(r), 1 + r
def step(x):
return 1 + (x << 2) - ((x >> 1) << 1)
def go(x):
root = floor(sqrt(x))
def p(qr):
q = qr[0]
return root < q or 0 == (x % q)
q = until(p)(f)(
(2 if 0 == x % 2 else 3, 1)
)[0]
return [x] if q > root else [q] + go(x // q)
return go(n)
# snd :: (a, b) -> b
def snd(tpl):
'''Second member of a pair.'''
return tpl[1]
# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.
'''
def go(f, x):
v = x
while not p(v):
v = f(v)
return v
return lambda f: lambda x: go(f, x)
# MAIN ---
if __name__ == '__main__':
main()</syntaxhighlight>
{{Out}}
<pre>Proper divisors of [1..10]:
1 -> []
2 -> [1]
3 -> [1]
4 -> [1, 2]
5 -> [1]
6 -> [1, 2, 3]
7 -> [1]
8 -> [1, 2, 4]
9 -> [1, 3]
10 -> [1, 2, 5]
Example of maximum divisor count in the range [1..20000]:
(15120, 79)</pre>
=== Python: The Simple Way ===
Not all the code submitters realized that it's a tie for the largest number of factors inside the limit. The task description clearly indicates only one answer is needed. But both numbers are provided for the curious. Also shown is the result for 25000, as there is no tie for that, just to show the program can handle either scenario.
<syntaxhighlight lang="python">def pd(num):
factors = []
for divisor in range(1,1+num//2):
if num % divisor == 0: factors.append(divisor)
return factors
def pdc(num):
count = 0
for divisor in range(1,1+num//2):
if num % divisor == 0: count += 1
return count
def fmtres(title, lmt, best, bestc):
return "The " + title + " number up to and including " + str(lmt) + " with the highest number of proper divisors is " + str(best) + ", which has " + str(bestc)
def showcount(limit):
best, bestc, bh, bhc = 0, 0, 0, 0
for i in range(limit+1):
divc = pdc(i)
if divc > bestc: bestc, best = divc, i
if divc >= bhc: bhc, bh = divc, i
if best == bh:
print(fmtres("only", limit, best, bestc))
else:
print(fmtres("lowest", limit, best, bestc))
print(fmtres("highest", limit, bh, bhc))
print()
lmt = 10
for i in range(1, lmt + 1):
divs = pd(i)
if len(divs) == 0:
print("There are no proper divisors of", i)
elif len(divs) == 1:
print(divs[0], "is the only proper divisor of", i)
else:
print(divs, "are the proper divisors of", i)
print()
showcount(20000)
showcount(25000)</syntaxhighlight>
{{out}}
<pre style="white-space: pre-wrap;">There are no proper divisors of 1
1 is the only proper divisor of 2
1 is the only proper divisor of 3
[1, 2] are the proper divisors of 4
1 is the only proper divisor of 5
[1, 2, 3] are the proper divisors of 6
1 is the only proper divisor of 7
[1, 2, 4] are the proper divisors of 8
[1, 3] are the proper divisors of 9
[1, 2, 5] are the proper divisors of 10
The lowest number up to and including 20000 with the highest number of proper divisors is 15120, which has 79
The highest number up to and including 20000 with the highest number of proper divisors is 18480, which has 79
The only number up to and including 25000 with the highest number of proper divisors is 20160, which has 83</pre>
=={{header|Quackery}}==
<code>factors</code> is defined at [[Factors of an integer#Quackery]].
<syntaxhighlight lang="quackery"> [ factors -1 split drop ] is properdivisors ( n --> [ )
10 times [ i^ 1+ properdivisors echo cr ]
0 0
20000 times
[ i^ 1+ properdivisors size
2dup < iff
[ dip [ 2drop i^ 1+ ] ]
else drop ]
swap echo say " has "
echo say " proper divisors." cr</syntaxhighlight>
{{out}}
<pre>[ ]
[ 1 ]
[ 1 ]
[ 1 2 ]
[ 1 ]
[ 1 2 3 ]
[ 1 ]
[ 1 2 4 ]
[ 1 3 ]
[ 1 2 5 ]
15120 has 79 proper divisors.
</pre>
=={{header|R}}==
===Package solution===
{{Works with|R|3.3.2 and above}}
<syntaxhighlight lang="rsplus"># Proper divisors. 12/10/16 aev
require(numbers);
V <- sapply(1:20000, Sigma, k = 0, proper = TRUE); ind <- which(V==max(V));
cat(" *** max number of divisors:", max(V), "\n"," *** for the following indices:",ind, "\n");</syntaxhighlight>
{{Output}}
<pre>Loading required package: numbers
*** max number of divisors: 79
*** for the following indices: 15120 18480 </pre>
===Filter solution===
<syntaxhighlight lang="rsplus">#Task 1
properDivisors <- function(N) Filter(function(x) N %% x == 0, seq_len(N %/% 2))
#Task 2
Vectorize(properDivisors)(1:10)
#Task 3
#Although there are two, the task only asks for one suitable number so that is all we give.
#Similarly, we have seen no need to make sure that "divisors" is only a plural when it should be.
#Be aware that this solution uses both length and lengths. It would not work if the index of the
#desired number was not also the number itself. However, this is always the case.
mostProperDivisors <- function(N)
{
divisorList <- Vectorize(properDivisors)(seq_len(N))
numberWithMostDivisors <- which.max(lengths(divisorList))
paste0("The number with the most proper divisors between 1 and ", N,
" is ", numberWithMostDivisors,
". It has ", length(divisorList[[numberWithMostDivisors]]),
" proper divisors.")
}
mostProperDivisors(20000)</syntaxhighlight>
{{Output}}
<pre>#Task 2
> Vectorize(properDivisors)(1:10)
[[1]]
integer(0)
[[2]]
[1] 1
[[3]]
[1] 1
[[4]]
[1] 1 2
[[5]]
[1] 1
[[6]]
[1] 1 2 3
[[7]]
[1] 1
[[8]]
[1] 1 2 4
[[9]]
[1] 1 3
[[10]]
[1] 1 2 5
#Task 3
> mostProperDivisors(20000)
[1] "The number with the most proper divisors between 1 and 20000 is 15120. It has 79 proper divisors."</pre>
=={{header|Racket}}==
Line 3,809 ⟶ 5,451:
=== Short version ===
<
(require math)
(define (proper-divisors n) (drop-right (divisors n) 1))
Line 3,819 ⟶ 5,461:
(if (< (length (cdr best)) (length divs)) (cons n divs) best)))
(printf "~a has ~a proper divisors\n"
(car most-under-20000) (length (cdr most-under-20000)))</
{{out}}
Line 3,838 ⟶ 5,480:
The '''main''' module will only be executed when this file is executed. When used as a library, it will not be used.
<
(provide fold-divisors ; name as per "Abundant..."
proper-divisors)
Line 3,875 ⟶ 5,517:
#:when [> c C])
(values c i)))
(printf "~a has ~a proper divisors\n" I C))</
The output is the same as the short version above.
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo|2018.10}}
Once your threshold is over 1000, the maximum proper divisors will always include 2, 3 and 5 as divisors, so only bother to check multiples of 2, 3 and 5.
There really isn't any point in using concurrency for a limit of 20_000. The setup and bookkeeping drowns out any benefit. Really doesn't start to pay off until the limit is 50_000 and higher. Try swapping in the commented out race map iterator line below for comparison.
<syntaxhighlight lang="raku" line>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
}
put "$_ [{propdiv($_)}]" for 1..10;
my @candidates;
loop (my int $c = 30; $c <= 20_000; $c += 30) {
#(30, *+30 …^ * > 500_000).race.map: -> $c {
my \mx = +propdiv($c);
next if mx < @candidates - 1;
@candidates[mx].push: $c
}
say "max = {@candidates - 1}, candidates = {@candidates.tail}";</syntaxhighlight>
{{out}}
<pre>1 []
2 [1]
3 [1]
4 [1 2]
5 [1]
6 [1 2 3]
7 [1]
8 [1 2 4]
9 [1 3]
10 [1 2 5]
max = 79, candidates = 15120 18480</pre>
=={{header|REXX}}==
===version 1===
<syntaxhighlight lang
/*REXX*/
Call time 'R'
Do x=1 To 10
Say x '->' proper_divisors(x)
Line 3,927 ⟶ 5,610:
count_proper_divisors: Procedure
Parse Arg n
Return words(proper_divisors(n))</
{{out}}
<pre>1 ->
Line 3,945 ⟶ 5,628:
===version 2===
The following REXX version is an adaptation of the ''optimized'' version for the REXX language example for
<br>code task: [https://www.rosettacode.org/wiki/Factors_of_an_integer ''Factors of an integer''].
This REXX version handles all integers (negative, zero, positive) and automatically adjusts the precision (decimal digits).
Line 3,952 ⟶ 5,636:
With the (function) optimization, it's over '''20''' times faster.
<
parse arg bot top inc range xtra /*obtain optional arguments from the CL*/
if bot=='' | bot=="," then bot= 1 /*Not specified? Then use the default.*/
Line 3,966 ⟶ 5,650:
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors: " q
end /*n*/
m=
do r=1 for range; q= Pdivs(r) /*process the second range specified. */
#= words(q); if #<m then iterate /*get proper divs; get number of Pdivs.*/
Line 3,982 ⟶ 5,666:
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors."
end /*i*/ /* [↑] support extra specified integers*/
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
Pdivs: procedure; parse arg x,b; x= abs(x); if x==1 then return '' /*unity?*/
Line 3,993 ⟶ 5,677:
/* [↓] adjust for a square. ___*/
if j*j==x then return a j b /*Was X a square? If so, add √ X */
return a b /*return the divisors (both lists). */</
{{out|output|text= when using the following input: <tt> 0 10 1 20000 166320 1441440 11796480000 </tt>}}
<pre>
Line 4,008 ⟶ 5,692:
10 has 3 proper divisors: 1 2 5
79 is the highest number of proper divisors in range 1──►20000, and it's for: 15120 and 18480
166320 has 159 proper divisors.
Line 4,020 ⟶ 5,704:
<br>When factoring 2,000,000 integers, this REXX version is about '''40%''' faster.
<br>When factoring 20,000,000 integers, this REXX version is about '''38%''' faster.
(The apparent slowdown for the last example above is probably due to a shortage of real storage, causing more page faults.)
It accomplishes a faster speed by incorporating the calculation of an ''integer square root'' of an integer (without using any floating point arithmetic).
<
parse arg bot top inc range xtra /*obtain optional arguments from the CL*/
if bot=='' | bot=="," then bot=
if top=='' | top=="," then top=
if inc=='' | inc=="," then inc=
if range=='' | range=="," then range=
w= max( length(top), length(bot), length(range)) /*determine the biggest number of these*/
numeric digits max(9, w + 1) /*have enough digits for // operator.*/
Line 4,036 ⟶ 5,722:
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors: " q
end /*n*/
m=
do r=1 for range; q= Pdivs(r) /*process the second range specified. */
#= words(q); if #<m then iterate /*get proper divs; get number of Pdivs.*/
Line 4,052 ⟶ 5,738:
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors."
end /*i*/ /* [↑] support extra specified integers*/
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
Pdivs: procedure; parse arg x 1 z,b; x= abs(x); if x==1 then return '' /*unity?*/
Line 4,067 ⟶ 5,753:
/* [↓] adjust for a square. ___*/
if j*j==x then return a j b /*Was X a square? If so, add √ X */
return a b /*return the divisors (both lists). */</
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version when using the same inputs.}} <br><br>
===version 4===
This REXX version uses an integer square root function to find the upper limit for the divisions.
For larger numbers, it is about '''7%''' faster.
<syntaxhighlight lang="rexx">/*REXX program finds proper divisors (and count) of integer ranges; finds the max count.*/
parse arg bot top inc range xtra /*obtain optional arguments from the CL*/
if bot=='' | bot=="," then bot= 1 /*Not specified? Then use the default.*/
if top=='' | top=="," then top= 10 /* " " " " " " */
if inc=='' | inc=="," then inc= 1 /* " " " " " " */
if range=='' | range=="," then range= 20000 /* " " " " " " */
w= max( length(top), length(bot), length(range)) /*determine the biggest number of these*/
numeric digits max(9, w + 1) /*have enough digits for // operator.*/
@.= 'and' /*a literal used to separate #s in list*/
do n=bot to top by inc /*process the first range specified. */
q= Pdivs(n); #= words(q) /*get proper divs; get number of Pdivs.*/
if q=='∞' then #= q /*adjust number of Pdivisors for zero. */
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors: " q
end /*n*/
m= 0 /*M ≡ maximum number of Pdivs (so far).*/
do r=1 for range; q= Pdivs(r) /*process the second range specified. */
#= words(q); if #<m then iterate /*get proper divs; get number of Pdivs.*/
if #<m then iterate /*Less then max? Then ignore this #. */
@.#= @.# @. r; m=# /*add this Pdiv to max list; set new M.*/
end /*r*/ /* [↑] process 2nd range of integers.*/
say
say m ' is the highest number of proper divisors in range 1──►'range,
", and it's for: " subword(@.m, 3)
say /* [↓] handle any given extra numbers.*/
do i=1 for words(xtra); n= word(xtra, i) /*obtain an extra number from XTRA list*/
w= max(w, 1 + length(n) ) /*use maximum width for aligned output.*/
numeric digits max(9, 1 + length(n) ) /*have enough digits for // operator.*/
q= Pdivs(n); #= words(q) /*get proper divs; get number of Pdivs.*/
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors."
end /*i*/ /* [↑] support extra specified integers*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
iSqrt: procedure; parse arg x; r=0; q=1; do while q<=x; q=q*4; end
do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end
return r
/*──────────────────────────────────────────────────────────────────────────────────────*/
Pdivs: procedure; parse arg x,b; x= abs(x)
if x==1 then return '' /*null set.*/
if x==0 then return '∞' /*infinity.*/
odd= x // 2 /*oddness of X. ___ */
r= iSqrt(x) /* obtain the integer √ X */
a= 1 /* [↓] use all, or only odd numbers. */
/* ___*/
if odd then do j=3 by 2 for r%2-(r*r==x) /*divide by some integers up to √ X */
if x//j==0 then do; a=a j; b=x%j b /*÷? Add both divisors to A & B*/
end
end /*j*/ /* ___*/
else do j=2 for r-1-(r*r==x) /*divide by some integers up to √ X */
if x//j==0 then do; a=a j; b=x%j b /*÷? Add both divisors to A & B*/
end
end /*j*/
if r*r==x then return a j b /*Was X a square? If so, add √ X */
return a b /*return proper divisors (both lists).*/</syntaxhighlight>
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version when using the same inputs.}} <br><br>
=={{header|Ring}}==
<
# Project : Proper divisors
Line 4,088 ⟶ 5,833:
see nl
next
</syntaxhighlight>
Output:
<pre>
Line 4,101 ⟶ 5,846:
9 -> 1 3
10 -> 1 2 5
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ DIVIS REVLIST TAIL REVLIST <span style="color:grey">@ or DIVIS 1 OVER SIZE 1 - SUB</span>
≫ '<span style="color:blue">PDIVIS</span>' STO
≪ 0 → max n
≪ 0
1 max '''FOR''' j
j <span style="color:blue">PDIVIS</span> SIZE
'''IF''' DUP2 < '''THEN''' SWAP j 'n' STO '''END'''
DROP
'''NEXT'''
DROP n DUP <span style="color:blue">PDIVIS</span> SIZE
≫ ≫ '<span style="color:blue">TASK2</span>' STO
≪ n <span style="color:blue">PDIVIS</span> ≫ 'n' 1 10 1 SEQ
20000 <span style="color:blue">TASK2</span>
{{out}}
<pre>
3: {{} {1} {1} {1 2} {1} {1 2 3} {1} {1 2 4} {1 3} {1 2 5}}
2: 15120
1: 39
</pre>
=={{header|Ruby}}==
<
class Integer
Line 4,121 ⟶ 5,890:
select.each do |n|
puts "#{n} has #{size} divisors"
end</
{{out}}
Line 4,140 ⟶ 5,909:
===An Alternative Approach===
<
#Nigel Galloway: December 23rd., 2014
require "prime"
Line 4,146 ⟶ 5,915:
(1..20000).each{|i| e = i.prime_division.inject(1){|n,g| n * (g[1]+1)}
n, g = e, i if e > n}
puts "#{g} has #{n-1} proper divisors"</
{{out}}
Line 4,161 ⟶ 5,930:
=={{header|Rust}}==
<
fn proper_divisors(&self) -> Option<Vec<u64>>;
}
Line 4,199 ⟶ 5,968:
most_divisors.len());
}
</syntaxhighlight>
{{out}}
<pre>Proper divisors of 1: []
Line 4,214 ⟶ 5,983:
</pre>
=={{header|S-
<syntaxhighlight lang="basic">
$lines
Line 4,238 ⟶ 6,007:
delta = 2
end
if n < 2 then count = 0 else count = 1
if display and (count = 1) then print using "#####"; 1;
i = start
limit = n / start
Line 4,279 ⟶ 6,048:
end
</syntaxhighlight>
{{out}}
<pre>
Proper divisors of first 10 numbers:
1 :
2 : 1
3 : 1
Line 4,301 ⟶ 6,070:
===Simple proper divisors===
<
def format(i: Int, divisors: Seq[Int]) = f"$i%5d ${divisors.length}%2d ${divisors mkString " "}"
Line 4,313 ⟶ 6,082:
}
list.foreach( number => println(f"$number%5d ${properDivisors(number).length}") )</
{{out}}
<pre> n cnt PROPER DIVISORS
Line 4,333 ⟶ 6,102:
If ''Long''s are enough to you you can replace every ''BigInt'' with ''Long'' and the one ''BigInt(1)'' with ''1L''
<
def factorize(x: BigInt): List[BigInt] = {
Line 4,350 ⟶ 6,119:
val products = (1 until factors.length).flatMap(i => factors.combinations(i).map(_.product).toList).toList
(BigInt(1) :: products).filter(_ < n)
}</
=={{header|Seed7}}==
<
const proc: writeProperDivisors (in integer: n) is func
Line 4,399 ⟶ 6,168:
end for;
writeln(max_i <& " with " <& max <& " divisors");
end func;</
{{out}}
Line 4,417 ⟶ 6,186:
=={{header|Sidef}}==
{{trans|
<
n.divisors.
}
Line 4,436 ⟶ 6,205:
}
say "max = #{max}, candidates = #{candidates}"</
{{out}}
<pre>
Line 4,454 ⟶ 6,223:
=={{header|Swift}}==
Simple function:
<
return filter (1 ..< n) { n % $0 == 0 }
}</
More efficient function:
<
func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }
Line 4,478 ⟶ 6,247:
return sorted(result)
}</
Rest of the task:
<
println("\(i): \(properDivs(i))")
}
Line 4,492 ⟶ 6,261:
}
println("\(num): \(max)")</
{{out}}
<pre>1: []
Line 4,508 ⟶ 6,277:
=={{header|tbas}}==
<syntaxhighlight lang="vb">
dim _proper_divisors(100)
Line 4,558 ⟶ 6,327:
print "A maximum at ";
show_proper_divisors(maxindex, false)
</syntaxhighlight>
<pre>
>tbas proper_divisors.bas
Line 4,581 ⟶ 6,350:
Note that if a number, <math>k</math>, greater than 1 divides <math>n</math> exactly, both <math>k</math> and <math>n/k</math> are
proper divisors. (The raw answers are not sorted; the pretty-printer code sorts.)
<
if {$n == 1} return
set divs 1
Line 4,606 ⟶ 6,375:
}
}
puts "max: $maxI => (...$maxC…)"</
{{out}}
<pre>
Line 4,622 ⟶ 6,391:
</pre>
=={{header|uBasic/4tH}}==
{{trans|True BASIC}}
<syntaxhighlight lang="text">LET m = 1
LET c = 0
PRINT "The proper divisors of the following numbers are:\n"
PROC _ListProperDivisors (10)
FOR n = 2 TO 20000
LET d = FUNC(_CountProperDivisors(n))
IF d > c THEN
LET c = d
LET m = n
ENDIF
NEXT
PRINT
PRINT m; " has the most proper divisors, namely "; c
END
_CountProperDivisors
PARAM (1)
LOCAL (2)
IF a@ < 2 THEN RETURN (0)
LET c@ = 0
FOR b@ = 1 TO a@ / 2
IF a@ % b@ = 0 THEN LET c@ = c@ + 1
NEXT
RETURN (c@)
_ListProperDivisors
PARAM (1)
LOCAL (2)
IF a@ < 1 THEN RETURN
FOR b@ = 1 TO a@
PRINT b@; " ->";
IF b@ = 1 THEN PRINT " (None)";
FOR c@ = 1 TO b@ / 2
IF b@ % c@ = 0 THEN PRINT " "; c@;
NEXT
PRINT
NEXT
RETURN</syntaxhighlight>
{{Out}}
<pre>The proper divisors of the following numbers are:
1 -> (None)
2 -> 1
3 -> 1
4 -> 1 2
5 -> 1
6 -> 1 2 3
7 -> 1
8 -> 1 2 4
9 -> 1 3
10 -> 1 2 5
15120 has the most proper divisors, namely 79
0 OK, 0:415</pre>
=={{header|VBA}}==
<
Dim t() As Long, i As Long, l As Long, j As Long, c As Long
For i = 1 To 10
Line 4,650 ⟶ 6,481:
End If
S = t
End Function</
{{out}}
<pre>Proper divisor of 1 :
Line 4,667 ⟶ 6,498:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Function ProperDivisors(number As Integer) As IEnumerable(Of Integer)
Line 4,682 ⟶ 6,513:
End Sub
End Module</
{{out}}
<pre>1: {}
Line 4,695 ⟶ 6,526:
10: {1, 2, 5}
15120: 79</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int
for (i in 1..10) System.print("%(Fmt.d(2, i)) -> %(Int.properDivisors(i))")
System.print("\nThe number in the range [1, 20000] with the most proper divisors is:")
var number = 1
var maxDivs = 0
for (i in 2..20000) {
var divs = Int.properDivisors(i).count
if (divs > maxDivs) {
number = i
maxDivs = divs
}
}
System.print("%(number) which has %(maxDivs) proper divisors.")</syntaxhighlight>
{{out}}
<pre>
1 -> []
2 -> [1]
3 -> [1]
4 -> [1, 2]
5 -> [1]
6 -> [1, 2, 3]
7 -> [1]
8 -> [1, 2, 4]
9 -> [1, 3]
10 -> [1, 2, 5]
The number in the range [1, 20000] with the most proper divisors is:
15120 which has 79 proper divisors.
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func PropDiv(N, Show); \Count and optionally show proper divisors of N
int N, Show, D, C;
[C:= 0;
if N > 1 then
[D:= 1;
repeat if rem(N/D) = 0 then
[C:= C+1;
if Show then
[if D > 1 then ChOut(0, ^ );
IntOut(0, D);
];
];
D:= D+1;
until D >= N;
];
return C;
];
int N, SN, Cnt, Max;
[for N:= 1 to 10 do
[ChOut(0, ^[); PropDiv(N, true); ChOut(0, ^]);
ChOut(0, ^ );
];
CrLf(0);
Max:= 0;
for N:= 1 to 20000 do
[Cnt:= PropDiv(N, false);
if Cnt > Max then
[Max:= Cnt; SN:= N];
];
IntOut(0, SN); ChOut(0, ^ ); IntOut(0, Max); CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
[] [1] [1] [1 2] [1] [1 2 3] [1] [1 2 4] [1 3] [1 2 5]
15120 79
</pre>
=={{header|zkl}}==
{{trans|D}}
This is the simple version :
<
This version is MUCH faster (the output isn't ordered however):
<
if(n==1) return(T);
( pd:=[1..(n).toFloat().sqrt()].filter('wrap(x){ n%x==0 }) )
.pump(pd,'wrap(pd){ if(pd!=1 and (y:=n/pd)!=pd ) y else Void.Skip })
}</
<
[1..20_001].apply('wrap(n){ T(properDivs(n).len(),n) })
.reduce(fcn([(a,_)]ab, [(c,_)]cd){ a>c and ab or cd },T(0,0))
.println();</
{{out}}
<pre>
|