Factors of an integer: Difference between revisions
add Refal
Not a robot (talk | contribs) (add Refal) |
|||
| (300 intermediate revisions by more than 100 users not shown) | |||
Line 1:
{{Task|Basic language learning}}
{{basic data operation}}
[[Category:Arithmetic operations]]
[[Category:Mathematical_operations]]
[[Category:Prime Numbers]]
;Task:
Compute the [[wp:Divisor|factors]] of a positive integer.
These factors are the positive integers by which the number being factored can be divided to yield a positive integer result.
(Though the concepts function correctly for zero and negative integers, the set of factors of zero has countably infinite members, and the factors of negative integers can be obtained from the factors of related positive numbers without difficulty; this task does not require handling of either of these cases).
Note that every prime number has two factors: '''1''' and itself.
;Related tasks:
* [[count in factors]]
* [[prime decomposition]]
* [[Sieve of Eratosthenes]]
* [[primality by trial division]]
* [[factors of a Mersenne number]]
* [[trial factoring of a Mersenne number]]
* [[partition an integer X into N primes]]
* [[sequence of primes by Trial Division]]
* [[sequence: smallest number greater than previous term with exactly n divisors]]
<br><br>
=={{header|0815}}==
<
<:1:~>|~#:end:>~x}:str:/={^:wei:~%x<:a:x=$~
=}:wei:x<:1:+{>~>x=-#:fin:^:str:}:fin:{{~%
</syntaxhighlight>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F factor(n)
V factors = Set[Int]()
L(x) 1..Int(sqrt(n))
I n % x == 0
factors.add(x)
factors.add(n I/ x)
R sorted(Array(factors))
L(i) (45, 53, 64)
print(i‘: factors: ’String(factor(i)))</syntaxhighlight>
{{out}}
<pre>
45: factors: [1, 3, 5, 9, 15, 45]
53: factors: [1, 53]
64: factors: [1, 2, 4, 8, 16, 32, 64]
</pre>
=={{header|360 Assembly}}==
Very compact version.
<syntaxhighlight lang="360asm">* Factors of an integer - 07/10/2015
FACTOR CSECT
USING FACTOR,R15 set base register
LA R7,PG pgi=@pg
LA R6,1 i
L R3,N loop count
LOOP L R5,N n
LA R4,0
DR R4,R6 n/i
LTR R4,R4 if mod(n,i)=0
BNZ NEXT
XDECO R6,PG+120 edit i
MVC 0(6,R7),PG+126 output i
LA R7,6(R7) pgi=pgi+6
NEXT LA R6,1(R6) i=i+1
BCT R3,LOOP loop
XPRNT PG,120 print buffer
XR R15,R15 set return code
BR R14 return to caller
N DC F'12345' <== input value
PG DC CL132' ' buffer
YREGS
END FACTOR</syntaxhighlight>
{{out}}
<pre>
1 3 5 15 823 2469 4115 12345
</pre>
=={{header|68000 Assembly}}==
<syntaxhighlight lang="68000devpac">;max input range equals 0 to 0xFFFFFFFF.
jsr GetInput ;unimplemented routine to get user input for a positive (nonzero) integer.
;output of this routine will be in D0.
MOVE.L D0,D1 ;D1 will be used for temp storage.
MOVE.L #1,D2 ;start with 1.
computeFactors:
DIVU D2,D1 ;remainder is in top 2 bytes, quotient in bottom 2.
MOVE.L D1,D3 ;temporarily store into D3 to check the remainder
SWAP D3 ;swap the high and low words of D3. Now bottom 2 bytes contain remainder.
CMP.W #0,D3 ;is the bottom word equal to 0?
BNE D2_Wasnt_A_Divisor ;if not, D2 was not a factor of D1.
JSR PrintD2 ;unimplemented routine to print D2 to the screen as a decimal number.
D2_Wasnt_A_Divisor:
MOVE.L D0,D1 ;restore D1.
ADDQ.L #1,D2 ;increment D2
CMP.L D2,D1 ;is D2 now greater than D1?
BLS computeFactors ;if not, loop again
;end of program</syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program factorst64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
.equ CHARPOS, '@'
/*******************************************/
/* Initialized data */
/*******************************************/
.data
szMessDeb: .ascii "Factors of : @ are : \n"
szMessFactor: .asciz "@ \n"
szCarriageReturn: .asciz "\n"
/*******************************************/
/* UnInitialized data */
/*******************************************/
.bss
sZoneConversion: .skip 100
/*******************************************/
/* code section */
/*******************************************/
.text
.global main
main: // entry of program
mov x0,#100
bl factors
mov x0,#97
bl factors
ldr x0,qNumber
bl factors
100: // standard end of the program
mov x0, #0 // return code
mov x8, #EXIT // request to exit program
svc 0 // perform the system call
qNumber: .quad 32767
qAdrszCarriageReturn: .quad szCarriageReturn
/******************************************************************/
/* calcul factors of number */
/******************************************************************/
/* x0 contains the number to factorize */
factors:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x5,x0 // limit calcul
ldr x1,qAdrsZoneConversion // conversion register in decimal string
bl conversion10S
ldr x0,qAdrszMessDeb // display message
ldr x1,qAdrsZoneConversion
bl strInsertAtChar
bl affichageMess
mov x6,#1 // counter loop
1: // loop
udiv x0,x5,x6 // division
msub x3,x0,x6,x5 // compute remainder
cbnz x3,2f // remainder not = zero -> loop
// display result if yes
mov x0,x6
ldr x1,qAdrsZoneConversion
bl conversion10S
ldr x0,qAdrszMessFactor // display message
ldr x1,qAdrsZoneConversion
bl strInsertAtChar
bl affichageMess
2:
add x6,x6,#1 // add 1 to loop counter
cmp x6,x5 // <= number ?
ble 1b // yes loop
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret
qAdrszMessDeb: .quad szMessDeb
qAdrszMessFactor: .quad szMessFactor
qAdrsZoneConversion: .quad sZoneConversion
/******************************************************************/
/* insert string at character insertion */
/******************************************************************/
/* x0 contains the address of string 1 */
/* x1 contains the address of insertion string */
/* x0 return the address of new string on the heap */
/* or -1 if error */
strInsertAtChar:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
stp x5,x6,[sp,-16]! // save registers
stp x7,x8,[sp,-16]! // save registers
mov x3,#0 // length counter
1: // compute length of string 1
ldrb w4,[x0,x3]
cmp w4,#0
cinc x3,x3,ne // increment to one if not equal
bne 1b // loop if not equal
mov x5,#0 // length counter insertion string
2: // compute length to insertion string
ldrb w4,[x1,x5]
cmp x4,#0
cinc x5,x5,ne // increment to one if not equal
bne 2b // and loop
cmp x5,#0
beq 99f // string empty -> error
add x3,x3,x5 // add 2 length
add x3,x3,#1 // +1 for final zero
mov x6,x0 // save address string 1
mov x0,#0 // allocation place heap
mov x8,BRK // call system 'brk'
svc #0
mov x5,x0 // save address heap for output string
add x0,x0,x3 // reservation place x3 length
mov x8,BRK // call system 'brk'
svc #0
cmp x0,#-1 // allocation error
beq 99f
mov x2,0
mov x4,0
3: // loop copy string begin
ldrb w3,[x6,x2]
cmp w3,0
beq 99f
cmp w3,CHARPOS // insertion character ?
beq 5f // yes
strb w3,[x5,x4] // no store character in output string
add x2,x2,1
add x4,x4,1
b 3b // and loop
5: // x4 contains position insertion
add x8,x4,1 // init index character output string
// at position insertion + one
mov x3,#0 // index load characters insertion string
6:
ldrb w0,[x1,x3] // load characters insertion string
cmp w0,#0 // end string ?
beq 7f // yes
strb w0,[x5,x4] // store in output string
add x3,x3,#1 // increment index
add x4,x4,#1 // increment output index
b 6b // and loop
7: // loop copy end string
ldrb w0,[x6,x8] // load other character string 1
strb w0,[x5,x4] // store in output string
cmp x0,#0 // end string 1 ?
beq 8f // yes -> end
add x4,x4,#1 // increment output index
add x8,x8,#1 // increment index
b 7b // and loop
8:
mov x0,x5 // return output string address
b 100f
99: // error
mov x0,#-1
100:
ldp x7,x8,[sp],16 // restaur 2 registers
ldp x5,x6,[sp],16 // restaur 2 registers
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<
(declare (xargs :measure (nfix (- n i))))
(cond ((zp (- n i))
Line 23 ⟶ 303:
(defun factors (n)
(factors-r n 1))</
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintFactors(CARD a)
BYTE notFirst
CARD p
p=1 notFirst=0
WHILE p<=a
DO
IF a MOD p=0 THEN
IF notFirst THEN
Print(", ")
FI
notFirst=1
PrintC(p)
FI
p==+1
OD
RETURN
PROC Test(CARD a)
PrintF("Factors of %U: ",a)
PrintFactors(a)
PutE()
RETURN
PROC Main()
Test(1)
Test(101)
Test(666)
Test(1977)
Test(2021)
Test(6502)
Test(12345)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Factors_of_an_integer.png Screenshot from Atari 8-bit computer]
<pre>
Factors of 1: 1
Factors of 101: 1, 101
Factors of 666: 1, 2, 3, 6, 9, 18, 37,74, 111, 222, 333, 666
Factors of 1977: 1, 3, 659, 1977
Factors of 2021: 1, 43, 47, 2021
Factors of 6502: 1, 2, 3251, 6502
Factors of 12345: 1, 3, 5, 15, 823, 2469, 4115, 12345
</pre>
=={{header|ActionScript}}==
<
{
var factors:Vector.<uint> = new Vector.<uint>();
Line 32 ⟶ 358:
if(n % i == 0)factors.push(i);
return factors;
}</
=={{header|Ada}}==
<
with Ada.Command_Line;
procedure Factors is
Line 56 ⟶ 382:
end loop;
Ada.Text_IO.Put_Line (Positive'Image (Number) & ".");
end Factors;</
=={{header|Aikido}}==
<
function factor (n:int) {
Line 92 ⟶ 418:
printvec (factor (45))
printvec (factor (25))
printvec (factor (100))</
=={{header|ALGOL 68}}==
Line 102 ⟶ 428:
Note: The following implements generators, eliminating the need of declaring arbitrarily long '''int''' arrays for caching.
<
PROC gen factors = (INT n, YIELDINT yield)VOID: (
Line 126 ⟶ 452:
# OD # ));
print(new line)
OD</
{{out}}
<pre>
+45: 1, 45, 3, 15, 5, 9
Line 133 ⟶ 459:
+64: 1, 64, 2, 32, 4, 16, 8
</pre>
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw">begin
% return the factors of n ( n should be >= 1 ) in the array factor %
% the bounds of factor should be 0 :: len (len must be at least 1) %
% the number of factors will be returned in factor( 0 ) %
procedure getFactorsOf ( integer value n
; integer array factor( * )
; integer value len
) ;
begin
for i := 0 until len do factor( i ) := 0;
if n >= 1 and len >= 1 then begin
integer pos, lastFactor;
factor( 0 ) := factor( 1 ) := pos := 1;
% find the factors up to sqrt( n ) %
for f := 2 until truncate( sqrt( n ) ) + 1 do begin
if ( n rem f ) = 0 and pos <= len then begin
% found another factor and there's room to store it %
pos := pos + 1;
factor( 0 ) := pos;
factor( pos ) := f
end if_found_factor
end for_f;
% find the factors above sqrt( n ) %
lastFactor := factor( factor( 0 ) );
for f := factor( 0 ) step -1 until 1 do begin
integer newFactor;
newFactor := n div factor( f );
if newFactor > lastFactor and pos <= len then begin
% found another factor and there's room to store it %
pos := pos + 1;
factor( 0 ) := pos;
factor( pos ) := newFactor
end if_found_factor
end for_f;
end if_params_ok
end getFactorsOf ;
% prpocedure to test getFactorsOf %
procedure testFactorsOf( integer value n ) ;
begin
integer array factor( 0 :: 100 );
getFactorsOf( n, factor, 100 );
i_w := 1; s_w := 0; % set output format %
write( n, " has ", factor( 0 ), " factors:" );
for f := 1 until factor( 0 ) do writeon( " ", factor( f ) )
end testFactorsOf ;
% test the factorising %
for i := 1 until 100 do testFactorsOf( i )
end.</syntaxhighlight>
{{out}}
<pre>
1 has 1 factors: 1
2 has 2 factors: 1 2
3 has 2 factors: 1 3
4 has 3 factors: 1 2 4
...
96 has 12 factors: 1 2 3 4 6 8 12 16 24 32 48 96
97 has 2 factors: 1 97
98 has 6 factors: 1 2 7 14 49 98
99 has 6 factors: 1 3 9 11 33 99
100 has 9 factors: 1 2 4 5 10 20 25 50 100
</pre>
=={{header|ALGOL-M}}==
Instead of displaying 1 and the number itself as factors, prime numbers are explicitly reported as such. To reduce the number of test divisions, only odd divisors are tested if an initial check shows the number to be factored is not even. The upper limit of divisors is set at N/2 or N/3, depending on whether N is even or odd, and is continuously reduced to N divided by the next potential divisor until the first factor is found. For a prime number the resulting limit will be the square root of N, which avoids the necessity of explicitly calculating that value. (ALGOL-M does not have a built-in square root function.)
<syntaxhighlight lang="algol">
BEGIN
COMMENT RETURN P MOD Q;
INTEGER FUNCTION MOD (P, Q);
INTEGER P, Q;
BEGIN
MOD := P - Q * (P / Q);
END;
INTEGER I, N, LIMIT, FOUND, START, DELTA;
WHILE 1 = 1 DO
BEGIN
WRITE ("NUMBER TO FACTOR (OR 0 TO QUIT):");
READ (N);
IF N = 0 THEN GOTO DONE;
WRITE ("THE FACTORS ARE:");
COMMENT CHECK WHETHER NUMBER IS EVEN OR ODD;
IF MOD(N, 2) = 0 THEN
BEGIN
START := 2;
DELTA := 1;
END
ELSE
BEGIN
START := 3;
DELTA := 2;
END;
COMMENT TEST POTENTIAL DIVISORS;
FOUND := 0;
I := START;
LIMIT := N / I;
WHILE I <= LIMIT DO
BEGIN
IF MOD(N, I) = 0 THEN
BEGIN
WRITEON (I);
FOUND := FOUND + 1;
END;
I := I + DELTA;
IF FOUND = 0 THEN LIMIT := N / I;
END;
IF FOUND = 0 THEN WRITEON (" NONE - THE NUMBER IS PRIME.");
WRITE("");
END;
DONE: WRITE ("GOODBYE");
END</syntaxhighlight>
{{out}}
<pre>NUMBER TO FACTOR (OR 0 TO QUIT):
-> 96
THE FACTORS ARE: 2 3 4 6 8 12 16 24 32 48
NUMBER TO FACTOR (OR 0 TO QUIT):
-> 97
THE FACTORS ARE: NONE - THE NUMBER IS PRIME.
NUMBER TO FACTOR (OR 0 TO QUIT):
-> 98
THE FACTORS ARE: 2 7 14 49
NUMBER TO FACTOR (OR 0 TO QUIT):
-> 0
GOODBYE</pre>
=={{header|APL}}==
<
factors 12345
1 3 5 15 823 2469 4115 12345
factors 720
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 36 40 45 48 60 72 80 90 120 144 180 240 360 720</
=={{header|AppleScript}}==
===Functional===
{{Trans|JavaScript}}
<syntaxhighlight lang="applescript">-- integerFactors :: Int -> [Int]
on integerFactors(n)
if n = 1 then
{1}
else if 1 > n then
missing value
else
set realRoot to n ^ (1 / 2)
set intRoot to realRoot as integer
set blnPerfectSquare to intRoot = realRoot
-- isFactor :: Int -> Bool
script isFactor
on |λ|(x)
(n mod x) = 0
end |λ|
end script
-- Factors up to square root of n,
set lows to filter(isFactor, enumFromTo(1, intRoot))
-- integerQuotient :: Int -> Int
script integerQuotient
on |λ|(x)
(n / x) as integer
end |λ|
end script
-- and quotients of these factors beyond the square root.
lows & map(integerQuotient, ¬
items (1 + (blnPerfectSquare as integer)) thru -1 of reverse of lows)
end if
end integerFactors
--------------------------- TEST -------------------------
on run
integerFactors(120)
--> {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120}
end run
-------------------- GENERIC FUNCTIONS -------------------
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if n < m then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
-- filter :: (a -> Bool) -> [a] -> [a]
on filter(f, xs)
tell mReturn(f)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |λ|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="applescript">{1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120}</syntaxhighlight>
----
===Straightforward===
<syntaxhighlight lang="applescript">on factors(n)
set output to {}
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 1 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
return output
end factors
factors(123456789)</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{1, 3, 9, 3607, 3803, 10821, 11409, 32463, 34227, 13717421, 41152263, 123456789}</syntaxhighlight>
=={{header|Arc}}==
<syntaxhighlight lang="arc">
(= divisor (fn (num)
(= dlist '())
(when (is 1 num) (= dlist '(1 0)))
(when (is 2 num) (= dlist '(2 1)))
(unless (or (is 1 num) (is 2 num))
(up i 1 (+ 1 (/ num 2))
(if (is 0 (mod num i))
(push i dlist)))
(= dlist (cons num dlist)))
dlist))
(map [rev _] (map [divisor _] '(45 53 60 64)))
</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="arc">
'(
(1 3 5 9 15 45)
(1 53)
(1 2 3 4 5 6 10 12 15 20 30 60)
(1 2 4 8 16 32 64)
)
</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program factorst.s */
/* Constantes */
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
/* Initialized data */
.data
szMessDeb: .ascii "Factors of :"
sMessValeur: .fill 12, 1, ' '
.asciz "are : \n"
sMessFactor: .fill 12, 1, ' '
.asciz "\n"
szCarriageReturn: .asciz "\n"
/* UnInitialized data */
.bss
/* code section */
.text
.global main
main: /* entry of program */
push {fp,lr} /* saves 2 registers */
mov r0,#100
bl factors
mov r0,#97
bl factors
ldr r0,iNumber
bl factors
100: /* standard end of the program */
mov r0, #0 @ return code
pop {fp,lr} @restaur 2 registers
mov r7, #EXIT @ request to exit program
swi 0 @ perform the system call
iNumber: .int 32767
iAdrszCarriageReturn: .int szCarriageReturn
/******************************************************************/
/* calcul factors of number */
/******************************************************************/
/* r0 contains the number */
factors:
push {fp,lr} /* save registres */
push {r1-r6} /* save others registers */
mov r5,r0 @ limit calcul
ldr r1,iAdrsMessValeur @ conversion register in decimal string
bl conversion10S
ldr r0,iAdrszMessDeb @ display message
bl affichageMess
mov r6,#1 @ counter loop
1: @ loop
mov r0,r5 @ dividende
mov r1,r6 @ divisor
bl division
cmp r3,#0 @ remainder = zero ?
bne 2f
@ display result if yes
mov r0,r6
ldr r1,iAdrsMessFactor
bl conversion10S
ldr r0,iAdrsMessFactor
bl affichageMess
2:
add r6,#1 @ add 1 to loop counter
cmp r6,r5 @ <= number ?
ble 1b @ yes loop
100:
pop {r1-r6} /* restaur others registers */
pop {fp,lr} /* restaur des 2 registres */
bx lr /* return */
iAdrsMessValeur: .int sMessValeur
iAdrszMessDeb: .int szMessDeb
iAdrsMessFactor: .int sMessFactor
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {fp,lr} /* save registres */
push {r0,r1,r2,r7} /* save others registers */
mov r2,#0 /* counter length */
1: /* loop length calculation */
ldrb r1,[r0,r2] /* read octet start position + index */
cmp r1,#0 /* if 0 its over */
addne r2,r2,#1 /* else add 1 in the length */
bne 1b /* and loop */
/* so here r2 contains the length of the message */
mov r1,r0 /* address message in r1 */
mov r0,#STDOUT /* code to write to the standard output Linux */
mov r7, #WRITE /* code call system "write" */
swi #0 /* call systeme */
pop {r0,r1,r2,r7} /* restaur others registers */
pop {fp,lr} /* restaur des 2 registres */
bx lr /* return */
/*=============================================*/
/* division integer unsigned */
/*============================================*/
division:
/* r0 contains N */
/* r1 contains D */
/* r2 contains Q */
/* r3 contains R */
push {r4, lr}
mov r2, #0 /* r2 ? 0 */
mov r3, #0 /* r3 ? 0 */
mov r4, #32 /* r4 ? 32 */
b 2f
1:
movs r0, r0, LSL #1 /* r0 ? r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1) */
adc r3, r3, r3 /* r3 ? r3 + r3 + C. This is equivalent to r3 ? (r3 << 1) + C */
cmp r3, r1 /* compute r3 - r1 and update cpsr */
subhs r3, r3, r1 /* if r3 >= r1 (C=1) then r3 ? r3 - r1 */
adc r2, r2, r2 /* r2 ? r2 + r2 + C. This is equivalent to r2 ? (r2 << 1) + C */
2:
subs r4, r4, #1 /* r4 ? r4 - 1 */
bpl 1b /* if r4 >= 0 (N=0) then branch to .Lloop1 */
pop {r4, lr}
bx lr
/***************************************************/
/* conversion register in string décimal signed */
/***************************************************/
/* r0 contains the register */
/* r1 contains address of conversion area */
conversion10S:
push {fp,lr} /* save registers frame and return */
push {r0-r5} /* save other registers */
mov r2,r1 /* early storage area */
mov r5,#'+' /* default sign is + */
cmp r0,#0 /* négatif number ? */
movlt r5,#'-' /* yes sign is - */
mvnlt r0,r0 /* and inverse in positive value */
addlt r0,#1
mov r4,#10 /* area length */
1: /* conversion loop */
bl divisionpar10 /* division */
add r1,#48 /* add 48 at remainder for conversion ascii */
strb r1,[r2,r4] /* store byte area r5 + position r4 */
sub r4,r4,#1 /* previous position */
cmp r0,#0
bne 1b /* loop if quotient not equal zéro */
strb r5,[r2,r4] /* store sign at current position */
subs r4,r4,#1 /* previous position */
blt 100f /* if r4 < 0 end */
/* else complete area with space */
mov r3,#' ' /* character space */
2:
strb r3,[r2,r4] /* store byte */
subs r4,r4,#1 /* previous position */
bge 2b /* loop if r4 greather or equal zero */
100: /* standard end of function */
pop {r0-r5} /*restaur others registers */
pop {fp,lr} /* restaur des 2 registers frame et return */
bx lr
/***************************************************/
/* division par 10 signé */
/* Thanks to http://thinkingeek.com/arm-assembler-raspberry-pi/*
/* and http://www.hackersdelight.org/ */
/***************************************************/
/* r0 contient le dividende */
/* r0 retourne le quotient */
/* r1 retourne le reste */
divisionpar10:
/* r0 contains the argument to be divided by 10 */
push {r2-r4} /* save autres registres */
mov r4,r0
ldr r3, .Ls_magic_number_10 /* r1 <- magic_number */
smull r1, r2, r3, r0 /* r1 <- Lower32Bits(r1*r0). r2 <- Upper32Bits(r1*r0) */
mov r2, r2, ASR #2 /* r2 <- r2 >> 2 */
mov r1, r0, LSR #31 /* r1 <- r0 >> 31 */
add r0, r2, r1 /* r0 <- r2 + r1 */
add r2,r0,r0, lsl #2 /* r2 <- r0 * 5 */
sub r1,r4,r2, lsl #1 /* r1 <- r4 - (r2 * 2) = r4 - (r0 * 10) */
pop {r2-r4}
bx lr /* leave function */
.align 4
.Ls_magic_number_10: .word 0x66666667
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">factors: $[num][
select 1..num [x][
(num%x)=0
]
]
print factors 36</syntaxhighlight>
{{out}}
<pre>1 2 3 4 6 9 12 18 36</pre>
=={{header|Asymptote}}==
<syntaxhighlight lang="asymptote">int[] n = {11, 21, 32, 45, 67, 519};
for(var j : n) {
write(j, suffix=none);
write(" =>", suffix=none);
for(int i = 1; i < (j/2); ++i) {
if(j % i == 0) {
write(" ", i, suffix=none);
}
}
write(" ", j);
}</syntaxhighlight>
{{out}}
<pre>11 => 1 11
21 => 1 3 7 21
32 => 1 2 4 8 32
45 => 1 3 5 9 15 45
67 => 1 67
519 => 1 3 173 519</pre>
=={{header|AutoHotkey}}==
<
Factors(n)
Line 150 ⟶ 994:
Sort, v, N U D,
Return, v
}</
{{out}}
<pre>
1,3,5,9,15,45
1,53
Line 158 ⟶ 1,003:
=={{header|AutoIt}}==
<
$num = 45
MsgBox (0,"Factors", "Factors of " & $num & " are: " & factors($num))
Line 170 ⟶ 1,015:
Next
Return $ls_factors&$intg
EndFunc</
{{out}}
<pre>
Factors of 45 are: 1, 3, 5, 9, 15, 45
</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f FACTORS_OF_AN_INTEGER.AWK
BEGIN {
Line 197 ⟶ 1,042:
printf("\n")
}
</syntaxhighlight>
{{out}}
<pre>
enter a number or C/R to exit
Line 211 ⟶ 1,057:
factors of 32767: 1 7 31 151 217 1057 4681 32767
</pre>
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
The [[Factors_of_an_integer#Sinclair ZX81 BASIC]] code works the same in Applesoft BASIC.
==={{header|ASIC}}===
{{trans|GW-BASIC}}
<syntaxhighlight lang="basic">REM Factors of an integer
PRINT "Enter an integer";
LOOP:
INPUT N
IF N = 0 THEN LOOP:
NA = ABS(N)
NDIV2 = NA / 2
FOR I = 1 TO NDIV2
NMODI = NA MOD I
IF NMODI = 0 THEN
PRINT I;
ENDIF
NEXT I
PRINT NA
END</syntaxhighlight>
{{out}}
<pre>Enter an integer?60
1 2 3 4 5 6 10 12 15 20 30 60</pre>
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">
subroutine printFactors(n)
print n; " => ";
for i = 1 to n / 2
if n mod i = 0 then print i; " ";
next i
print n
end subroutine
call printFactors(11)
call printFactors(21)
call printFactors(32)
call printFactors(45)
call printFactors(67)
call printFactors(96)
end</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic"> INSTALL @lib$+"SORTLIB"
sort% = FN_sortinit(0, 0)
PRINT "The factors of 45 are " FNfactorlist(45)
PRINT "The factors of 12345 are " FNfactorlist(12345)
END
DEF FNfactorlist(N%)
LOCAL C%, I%, L%(), L$
DIM L%(32)
FOR I% = 1 TO SQR(N%)
IF (N% MOD I% = 0) THEN
L%(C%) = I%
C% += 1
IF (N% <> I%^2) THEN
L%(C%) = (N% DIV I%)
C% += 1
ENDIF
ENDIF
NEXT I%
CALL sort%, L%(0)
FOR I% = 0 TO C%-1
L$ += STR$(L%(I%)) + ", "
NEXT
= LEFT$(LEFT$(L$))</syntaxhighlight>
{{out}}
<pre>The factors of 45 are 1, 3, 5, 9, 15, 45
The factors of 12345 are 1, 3, 5, 15, 823, 2469, 4115, 12345</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|BASIC256}}
<syntaxhighlight lang="qbasic">10 cls
20 printfactors(11)
30 printfactors(21)
40 printfactors(32)
50 printfactors(45)
60 printfactors(67)
70 printfactors(96)
80 end
100 sub printfactors(n)
110 if n < 1 then printfactors = 0
120 print n "=> ";
130 for i = 1 to n/2
140 if n mod i = 0 then print i " ";
150 next i
160 print n
170 end sub</syntaxhighlight>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">do
input "enter an integer", n
loop n = 0
let a = abs(n)
for i = 1 to int(a / 2)
if a = int(a / i) * i then
print i
endif
next i
print a</syntaxhighlight>
{{out| Output}}<pre>?60
1 2 3 4 5 6 10 12 15 20 30 60</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
Sub printFactors(n As Integer)
If n < 1 Then Return
Print n; " =>";
For i As Integer = 1 To n / 2
If n Mod i = 0 Then Print i; " ";
Next i
Print n
End Sub
printFactors(11)
printFactors(21)
printFactors(32)
printFactors(45)
printFactors(67)
printFactors(96)
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
{{out}}
<pre>
11 => 1 11
21 => 1 3 7 21
32 => 1 2 4 8 16 32
45 => 1 3 5 9 15 45
67 => 1 67
96 => 1 2 3 4 6 8 12 16 24 32 48 96
</pre>
==={{header|FutureBasic}}===
<syntaxhighlight lang="futurebasic">window 1, @"Factors of an Integer", (0,0,1000,270)
clear local mode
local fn IntegerFactors( f as long ) as CFStringRef
long i, s, l(100), c = 0
CFStringRef factorStr = @""
for i = 1 to sqr(f)
if ( f mod i == 0 )
l(c) = i
c++
if ( f != i ^ 2 )
l(c) = ( f / i )
c++
end if
end if
next i
s = 1
while ( s = 1 )
s = 0
for i = 0 to c-1
if l(i) > l(i+1) and l(i+1) != 0
swap l(i), l(i+1)
s = 1
end if
next i
wend
for i = 0 to c - 1
if ( i < c - 1 )
factorStr = fn StringWithFormat( @"%@ %ld, ", factorStr, l(i) )
else
factorStr = fn StringWithFormat( @"%@ %ld", factorStr, l(i) )
end if
next
end fn = factorStr
print @"Factors of 25 are:"; fn IntegerFactors( 25 )
print @"Factors of 45 are:"; fn IntegerFactors( 45 )
print @"Factors of 103 are:"; fn IntegerFactors( 103 )
print @"Factors of 760 are:"; fn IntegerFactors( 760 )
print @"Factors of 12345 are:"; fn IntegerFactors( 12345 )
print @"Factors of 32766 are:"; fn IntegerFactors( 32766 )
print @"Factors of 32767 are:"; fn IntegerFactors( 32767 )
print @"Factors of 57097 are:"; fn IntegerFactors( 57097 )
print @"Factors of 12345678 are:"; fn IntegerFactors( 12345678 )
print @"Factors of 32434243 are:"; fn IntegerFactors( 32434243 )
HandleEvents</syntaxhighlight>
{{out}}
<pre>Factors of 25 are: 1, 5, 25
Factors of 45 are: 1, 3, 5, 9, 15, 45
Factors of 103 are: 1, 103
Factors of 760 are: 1, 2, 4, 5, 8, 10, 19, 20, 38, 40, 76, 95, 152, 190, 380, 760
Factors of 12345 are: 1, 3, 5, 15, 823, 2469, 4115, 12345
Factors of 32766 are: 1, 2, 3, 6, 43, 86, 127, 129, 254, 258, 381, 762, 5461, 10922, 16383, 32766
Factors of 32767 are: 1, 7, 31, 151, 217, 1057, 4681, 32767
Factors of 57097 are: 1, 57097
Factors of 12345678 are: 1, 2, 3, 6, 9, 18, 47, 94, 141, 282, 423, 846, 14593, 29186, 43779, 87558, 131337, 262674, 685871, 1371742, 2057613, 4115226, 6172839, 12345678
Factors of 32434243 are: 1, 307, 105649, 32434243</pre>
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Public Sub Main()
printFactors(11)
printFactors(21)
printFactors(32)
printFactors(45)
printFactors(67)
printFactors(96)
End
Sub printFactors(n As Integer)
If n < 1 Then Return
Print n; " =>";
For i As Integer = 1 To n / 2
If n Mod i = 0 Then Print i; " ";
Next
Print n
End Sub</syntaxhighlight>
==={{header|GW-BASIC}}===
<syntaxhighlight lang="qbasic">
10 INPUT "Enter an integer: ", N
20 IF N = 0 THEN GOTO 10
30 NA = ABS(N)
40 FOR I = 1 TO NA/2
50 IF NA MOD I = 0 THEN PRINT I;
60 NEXT I
70 PRINT NA</syntaxhighlight>
{{out}}
<pre>
Enter an integer: 1
1
Enter an integer: 12
1 2 3 4 6 12
Enter an integer: 13
1 13
Enter an integer: -22222
1 2 41 82 271 542 11111 22222
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="qbasic">100 PROGRAM "Factors.bas"
110 INPUT PROMPT "Number: ":N
120 FOR I=1 TO INT(N/2)
130 IF MOD(N,I)=0 THEN PRINT I;
140 NEXT
150 PRINT N</syntaxhighlight>
==={{header|Liberty BASIC}}===
<syntaxhighlight lang="lb">num = 10677106534462215678539721403561279
maxnFactors = 1000
dim primeFactors(maxnFactors), nPrimeFactors(maxnFactors)
global nDifferentPrimeNumbersFound, nFactors, iFactor
print "Start finding all factors of ";num; ":"
nDifferentPrimeNumbersFound=0
dummy = factorize(num,2)
nFactors = showPrimeFactors(num)
dim factors(nFactors)
dummy = generateFactors(1,1)
sort factors(), 0, nFactors-1
for i=1 to nFactors
print i;" ";factors(i-1)
next i
print "done"
wait
function factorize(iNum,offset)
factorFound=0
i = offset
do
if (iNum MOD i)=0 _
then
if primeFactors(nDifferentPrimeNumbersFound) = i _
then
nPrimeFactors(nDifferentPrimeNumbersFound) = nPrimeFactors(nDifferentPrimeNumbersFound) + 1
else
nDifferentPrimeNumbersFound = nDifferentPrimeNumbersFound + 1
primeFactors(nDifferentPrimeNumbersFound) = i
nPrimeFactors(nDifferentPrimeNumbersFound) = 1
end if
if iNum/i<>1 then dummy = factorize(iNum/i,i)
factorFound=1
end if
i=i+1
loop while factorFound=0 and i<=sqr(iNum)
if factorFound=0 _
then
nDifferentPrimeNumbersFound = nDifferentPrimeNumbersFound + 1
primeFactors(nDifferentPrimeNumbersFound) = iNum
nPrimeFactors(nDifferentPrimeNumbersFound) = 1
end if
end function
function showPrimeFactors(iNum)
showPrimeFactors=1
print iNum;" = ";
for i=1 to nDifferentPrimeNumbersFound
print primeFactors(i);"^";nPrimeFactors(i);
if i<nDifferentPrimeNumbersFound then print " * "; else print ""
showPrimeFactors = showPrimeFactors*(nPrimeFactors(i)+1)
next i
end function
function generateFactors(product,pIndex)
if pIndex>nDifferentPrimeNumbersFound _
then
factors(iFactor) = product
iFactor=iFactor+1
else
for i=0 to nPrimeFactors(pIndex)
dummy = generateFactors(product*primeFactors(pIndex)^i,pIndex+1)
next i
end if
end function</syntaxhighlight>
{{out}}
<syntaxhighlight lang="lb">Start finding all factors of 10677106534462215678539721403561279:
10677106534462215678539721403561279 = 29269^1 * 32579^1 * 98731^2 * 104729^3
1 1
2 29269
3 32579
4 98731
5 104729
6 953554751
7 2889757639
8 3065313101
9 3216557249
10 3411966091
11 9747810361
12 10339998899
13 10968163441
14 94145414120981
15 99864835517479
16 285308661456109
17 302641427774831
18 317573913751019
19 321027175754629
20 336866824130521
21 357331796744339
22 1020878431297169
23 1082897744693371
24 1148684789012489
25 9295070881578575111
26 9859755075476219149
27 10458744358910058191
28 29880090805636839461
29 31695334089430275799
30 33259198413230468851
31 33620855089606540541
32 35279725624365333809
33 37423001741237879131
34 106915577231321212201
35 113410797903992051459
36 973463478356842592799919
37 1032602289299548955255621
38 1095333837964291484285239
39 3129312029983540559911069
40 3319420643851943354153471
41 3483202590619213772296379
42 3694810384914157044482761
43 11197161487859039232598529
44 101949856624833767901342716951
45 108143405156052462534965931709
46 327729719588146219298926345301
47 364792324112959639158827476291
48 10677106534462215678539721403561279
done</syntaxhighlight>
====A Simpler Approach====
This is a somewhat simpler approach for finding the factors of smaller numbers (less than one million).
{{works with|Just BASIC}}
<syntaxhighlight lang="lb">
print "ROSETTA CODE - Factors of an integer"
'A simpler approach for smaller numbers
[Start]
print
input "Enter an integer (< 1,000,000): "; n
n=abs(int(n)): if n=0 then goto [Quit]
if n>999999 then goto [Start]
FactorCount=FactorCount(n)
select case FactorCount
case 1: print "The factor of 1 is: 1"
case else
print "The "; FactorCount; " factors of "; n; " are: ";
for x=1 to FactorCount
print " "; Factor(x);
next x
if FactorCount=2 then print " (Prime)" else print
end select
goto [Start]
[Quit]
print "Program complete."
end
function FactorCount(n)
dim Factor(100)
for y=1 to n
if y>sqr(n) and FactorCount=1 then
'If no second factor is found by the square root of n, then n is prime.
FactorCount=2: Factor(FactorCount)=n: exit function
end if
if (n mod y)=0 then
FactorCount=FactorCount+1
Factor(FactorCount)=y
end if
next y
end function
</syntaxhighlight>
{{out}}
<pre>
ROSETTA CODE - Factors of an integer
Enter an integer (< 1,000,000): 1
The factor of 1 is: 1
Enter an integer (< 1,000,000): 2
The 2 factors of 2 are: 1 2 (Prime)
Enter an integer (< 1,000,000): 4
The 3 factors of 4 are: 1 2 4
Enter an integer (< 1,000,000): 6
The 4 factors of 6 are: 1 2 3 6
Enter an integer (< 1,000,000): 999999
The 64 factors of 999999 are: 1 3 7 9 11 13 21 27 33 37 39 63 77 91 99 111 117 143 189 231 259 273 297 333 351 407 429 481 693 777 819 999 1001 1221 1287 1443 2079 2331 2457 2849 3003 3367 3663 3861 4329 5291 6993 8547 9009 10101 10989 12987 15873 25641 27027 30303 37037 47619 76923 90909 111111 142857 333333 999999
Enter an integer (< 1,000,000):
Program complete.
</pre>
==={{header|Minimal BASIC}}===
{{trans|GW-BASIC}}
{{works with|Commodore BASIC}}
{{works with|IS-BASIC}}
{{works with|MSX BASIC|any}}
{{works with|Nascom ROM BASIC|4.7}}
<syntaxhighlight lang="qbasic">10 REM Factors of an integer
20 PRINT "Enter an integer";
30 INPUT N
40 IF N = 0 THEN 30
50 N1 = ABS(N)
60 FOR I = 1 TO N1/2
70 IF INT(N1/I)*I <> N1 THEN 90
80 PRINT I;
90 NEXT I
100 PRINT N1
110 END</syntaxhighlight>
==={{header|MSX Basic}}===
{{trans|GW-BASIC}}
<syntaxhighlight lang="qbasic">10 INPUT "Enter an integer: "; N
20 IF N = 0 THEN GOTO 10
30 N1 = ABS(N)
40 FOR I = 1 TO N1/2
50 IF N1 MOD I = 0 THEN PRINT I;
60 NEXT I
70 PRINT N1</syntaxhighlight>
==={{header|Nascom BASIC}}===
{{trans|GW-BASIC}}
{{works with|Nascom ROM BASIC|4.7}}
<syntaxhighlight lang="basic">
10 REM Factors of an integer
20 INPUT "Enter an integer"; N
30 IF N=0 THEN 20
40 NA=ABS(N)
50 FOR I=1 TO INT(NA/2)
60 IF NA=INT(NA/I)*I THEN PRINT I;
70 NEXT I
80 PRINT NA
90 END
</syntaxhighlight>
{{out}}
<pre>Enter an integer? 60
1 2 3 4 5 6 10 12 15 20 30 60</pre>
See also [[#Minimal BASIC|Minimal BASIC]]
==={{header|Palo Alto Tiny BASIC}}===
{{trans|GW-BASIC}}
<syntaxhighlight lang="basic">
10 REM FACTORS OF AN INTEGER
20 INPUT "ENTER AN INTEGER"N
30 IF N=0 GOTO 20
40 LET A=ABS(N)
50 IF A=1 GOTO 90
60 FOR I=1 TO A/2
70 IF (A/I)*I=A PRINT I," ",
80 NEXT I
90 PRINT A
100 STOP
</syntaxhighlight>
{{out}}
3 runs.
<pre>ENTER AN INTEGER:1
1</pre>
<pre>ENTER AN INTEGER:60
1 2 3 4 5 6 10 12 15 20 30 60</pre>
<pre>ENTER AN INTEGER:-22222
1 2 41 82 271 542 11111 22222</pre>
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">Procedure PrintFactors(n)
Protected i, lim=Round(sqr(n),#PB_Round_Up)
NewList F.i()
For i=1 To lim
If n%i=0
AddElement(F()): F()=i
AddElement(F()): F()=n/i
EndIf
Next
;- Present the result
SortList(F(),#PB_Sort_Ascending)
ForEach F()
Print(str(F())+" ")
Next
EndProcedure
If OpenConsole()
Print("Enter integer to factorize: ")
PrintFactors(Val(Input()))
Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input()
EndIf</syntaxhighlight>
{{out}}
<pre> Enter integer to factorize: 96
1 2 3 4 6 8 12 16 24 32 48 96</pre>
==={{header|QB64}}===
<syntaxhighlight lang="qb64">'Task
'Compute the factors of a positive integer.
'These factors are the positive integers by which the number being factored can be divided to yield a positive integer result.
Dim Dividendum As Integer, Index As Integer
Randomize Timer
Dividendum = Int(Rnd * 1000) + 1
Print " Dividendum: "; Dividendum
Index = Int(Dividendum / 2)
print "Divisors: ";
While Index > 0
If Dividendum Mod Index = 0 Then Print Index; " ";
Index = Index - 1
Wend
End</syntaxhighlight>
==={{header|QBasic}}===
See [[#QuickBASIC|QuickBASIC]].
==={{header|QuickBASIC}}===
{{works with|QBasic}}
This example stores the factors in a shared array (with the original number as the last element) for later retrieval.
Note that this will error out if you pass 32767 (or higher).
<
REDIM SHARED factors(0) AS INTEGER
Line 249 ⟶ 1,665:
tmp(L1) = factors(L1)
NEXT
REDIM factors(UBOUND(factors) + 1) AS INTEGER
FOR L1 = 0 TO UBOUND(factors) - 1
factors(L1) = tmp(L1)
Line 256 ⟶ 1,672:
END IF
NEXT
END SUB</
{{out}}
<pre> Gimme a number? 17
1 , 17
Gimme a number? 12345
Line 267 ⟶ 1,682:
Gimme a number? 32766
1 , 2 , 3 , 6 , 43 , 86 , 127 , 129 , 254 , 258 , 381 , 762 , 5461 , 10922 ,
16383 , 32766</pre>
==={{header|Quite BASIC}}===
{{trans|GW-BASIC}}
<syntaxhighlight lang="qbasic">10 INPUT "Enter an integer: "; N
20 IF N = 0 THEN GOTO 15
30 N1 = ABS(N)
40 FOR I = 1 TO N1/2
50 IF N1 - INT(N1 / I) * I = 0 THEN PRINT I; " ";
60 NEXT I
70 PRINT N1</syntaxhighlight>
==={{header|REALbasic}}===
<syntaxhighlight lang="vb">Function factors(num As UInt64) As UInt64()
'This function accepts an unsigned 64 bit integer as input and returns an array of unsigned 64 bit integers
Dim result() As UInt64
Dim iFactor As UInt64 = 1
While iFactor <= num/2 'Since a factor will never be larger than half of the number
If num Mod iFactor = 0 Then
result.Append(iFactor)
End If
iFactor = iFactor + 1
Wend
result.Append(num) 'Since a given number is always a factor of itself
Return result
End Function</syntaxhighlight>
==={{header|Run BASIC}}===
<syntaxhighlight lang="basic">PRINT "Factors of 45 are ";factorlist$(45)
PRINT "Factors of 12345 are "; factorlist$(12345)
END
FUNCTION factorlist$(f)
DIM L(100)
FOR i = 1 TO SQR(f)
IF (f MOD i) = 0 THEN
L(c) = i
c = c + 1
IF (f <> i^2) THEN
L(c) = (f / i)
c = c + 1
END IF
END IF
NEXT i
s = 1
WHILE s = 1
s = 0
FOR i = 0 TO c-1
IF L(i) > L(i+1) AND L(i+1) <> 0 THEN
t = L(i)
L(i) = L(i+1)
L(i+1) = t
s = 1
END IF
NEXT i
WEND
FOR i = 0 TO c-1
factorlist$ = factorlist$ + STR$(L(i)) + ", "
NEXT
END FUNCTION</syntaxhighlight>
{{out}}
<pre>Factors of 45 are 1, 3, 5, 9, 15, 45,
Factors of 12345 are 1, 3, 5, 15, 823, 2469, 4115, 12345, </pre>
==={{header|Sinclair ZX81 BASIC}}===
{{works with|Applesoft BASIC}}
<syntaxhighlight lang="basic">10 INPUT N
20 FOR I=1 TO N
30 IF N/I=INT (N/I) THEN PRINT I;" ";
40 NEXT I</syntaxhighlight>
{{in}}
<pre>315</pre>
{{out}}
<pre>1 3 5 7 9 15 35 45 63 105 315</pre>
==={{header|Tiny BASIC}}===
{{works with|TinyBasic}}
<syntaxhighlight lang="basic">100 PRINT "Give me a number:"
110 INPUT I
120 LET C=1
130 PRINT "Factors of ",I,":"
140 IF I/C*C=I THEN PRINT C
150 LET C=C+1
160 IF C<=I THEN GOTO 140
170 END</syntaxhighlight>
{{out}}
<pre>Give me a number:
60
Factors of 60:
1
2
3
4
5
6
10
12
15
20
30
60</pre>
==={{header|True BASIC}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="qbasic">SUB printfactors(n)
IF n < 1 THEN EXIT SUB
PRINT n; "=>";
FOR i = 1 TO n / 2
IF REMAINDER(n, i) = 0 THEN PRINT i;
NEXT i
PRINT n
END SUB
CALL printfactors(11)
CALL printfactors(21)
CALL printfactors(32)
CALL printfactors(45)
CALL printfactors(67)
CALL printfactors(96)
END</syntaxhighlight>
==={{header|VBA}}===
<syntaxhighlight lang="vb">Function Factors(x As Integer) As String
Application.Volatile
Dim i As Integer
Dim cooresponding_factors As String
Factors = 1
corresponding_factors = x
For i = 2 To Sqr(x)
If x Mod i = 0 Then
Factors = Factors & ", " & i
If i <> x / i Then corresponding_factors = x / i & ", " & corresponding_factors
End If
Next i
If x <> 1 Then Factors = Factors & ", " & corresponding_factors
End Function</syntaxhighlight>
{{out}}
<pre>cell formula is "=Factors(840)"
resultant value is "1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 56, 60, 70, 84, 105, 120, 140, 168, 210, 280, 420, 840"</pre>
==={{header|XBasic}}===
{{trans|BASIC256}}
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "Factors of an integer"
VERSION "0.0000"
DECLARE FUNCTION Entry ()
DECLARE FUNCTION printFactors (n)
FUNCTION Entry ()
printFactors(11)
printFactors(21)
printFactors(32)
printFactors(45)
printFactors(67)
printFactors(96)
END FUNCTION
FUNCTION printFactors (n)
PRINT n; " =>";
FOR i = 1 TO n / 2
IF n MOD i = 0 THEN PRINT i; " ";
NEXT i
PRINT n
END FUNCTION
END PROGRAM</syntaxhighlight>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">sub printFactors(n)
if n < 1 return 0
print n, " =>";
for i = 1 to n / 2
if mod(n, i) = 0 print i, " ";
next i
print n
end sub
printFactors(11)
printFactors(21)
printFactors(32)
printFactors(45)
printFactors(67)
printFactors(96)
print
end</syntaxhighlight>
==={{header|ZX Spectrum Basic}}===
{{trans|AWK}}
<syntaxhighlight lang="basic">10 INPUT "Enter a number or 0 to exit: ";n
20 IF n=0 THEN STOP
30 PRINT "Factors of ";n;": ";
40 FOR i=1 TO n
50 IF FN m(n,i)=0 THEN PRINT i;" ";
60 NEXT i
70 DEF FN m(a,b)=a-INT (a/b)*b</syntaxhighlight>
=={{header|Batch File}}==
Command line version:
<
set res=Factors of %1:
for /L %%i in (1,1,%1) do call :fac %1 %%i
Line 279 ⟶ 1,889:
:fac
set /a test = %1 %% %2
if %test% equ 0 set res=%res% %2</
{{out}}
<pre>>factors 32767
Factors of 32767: 1 7 31 151 217 1057 4681 32767
Line 298 ⟶ 1,908:
Interactive version:
<
set /p limit=Gimme a number:
set res=Factors of %limit%:
Line 307 ⟶ 1,917:
:fac
set /a test = %1 %% %2
if %test% equ 0 set res=%res% %2</
{{out}}
<pre>>factors
Gimme a number:27
Line 318 ⟶ 1,927:
Gimme a number:102
Factors of 102: 1 2 3 6 17 34 51 102</pre>
=={{header|bc}}==
<
* This function mutates the global array f[] which will
* contain all factors of n in ascending order after the call!
Line 394 ⟶ 1,972:
scale = o
return(l)
}</
=={{header|Befunge}}==
<
>:0:g:*`| > >0:g1+0:p
>:0:g:*-#v_0:g\>$>:!#@_.v
> ^ ^ ," "<</
=={{header|BQN}}==
A bqncrate idiom.
<syntaxhighlight lang="bqn">Factors ← (1+↕)⊸(⊣/˜0=|)
•Show Factors 12345
•Show Factors 729</syntaxhighlight>
<syntaxhighlight lang="text">⟨ 1 3 5 15 823 2469 4115 12345 ⟩
⟨ 1 3 9 27 81 243 729 ⟩</syntaxhighlight>
The [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes] library from bqn-libs can be used for a solution that's more efficient for large inputs. <code>FactorExponents</code> returns each unique prime factor along with its exponent.
<syntaxhighlight lang="bqn">⟨FactorExponents⟩ ← •Import "primes.bqn" # With appropriate path
Factors ← { ∧⥊ 1 ×⌜´ ⋆⟜(↕1+⊢)¨˝ FactorExponents 𝕩 }</syntaxhighlight>
=={{header|Burlesque}}==
<syntaxhighlight lang="burlesque">blsq ) 32767 fc
{1 7 31 151 217 1057 4681 32767}</syntaxhighlight>
=={{header|C}}==
<
#include <stdlib.h>
Line 470 ⟶ 2,067:
}
return 0;
}</
===Prime factoring===
<
#include <stdlib.h>
#include <string.h>
Line 559 ⟶ 2,156:
return 0;
}</syntaxhighlight>
{{out}}
<pre>3: 1 3
120: 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
1024: 1 2 4 8 16 32 64 128 256 512 1024
3491888400: 1 2 3 4 5 6 7 8 9 10 11 ...(>1900 numbers)... 1163962800 1745944200 3491888400</pre>
=={{header|C sharp|C#}}==
===C# 1.0===
<syntaxhighlight lang="csharp">static void Main (string[] args) {
do {
Console.WriteLine ("Number:");
Int64 p = 0;
do {
try {
p = Convert.ToInt64 (Console.ReadLine ());
break;
} catch (Exception) { }
} while (true);
Console.WriteLine ("For 1 through " + ((int) Math.Sqrt (p)).ToString () + "");
for (int x = 1; x <= (int) Math.Sqrt (p); x++) {
if (p % x == 0)
Console.WriteLine ("Found: " + x.ToString () + ". " + p.ToString () + " / " + x.ToString () + " = " + (p / x).ToString ());
}
Console.WriteLine ("Done.");
} while (true);
}</syntaxhighlight>
{{out}}
<pre>Number:
32434243
For 1 through 5695
Found: 1. 32434243 / 1 = 32434243
Found: 307. 32434243 / 307 = 105649
Done.</pre>
===C# 3.0===
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
public static class Extension {
public static List<int> Factors (this int me) {
return Enumerable.Range (1, me).Where (x => me % x == 0).ToList ();
}
}
class Program {
static void Main (string[] args) {
Console.WriteLine (String.Join (", ", 45. Factors ()));
}
}</syntaxhighlight>
{{out}}
<pre>1, 3, 5, 9, 15, 45</pre>
=={{header|C++}}==
<
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iterator>
std::vector<int> GenerateFactors(int n) {
std::vector<int> factors = { 1, n };
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
factors.push_back(i);
if (i * i != n)
factors.push_back(n / i);
}
Line 590 ⟶ 2,236:
}
int main() {
const int SampleNumbers[] = { 3135, 45, 60, 81 };
for (size_t i = 0; i < sizeof(SampleNumbers) / sizeof(int); ++i) {
std::vector<int> factors = GenerateFactors(SampleNumbers[i]);
std::cout << "Factors of
std::cout.width(4);
std::cout << SampleNumbers[i] << " are: ";
std::copy(factors.begin(), factors.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
return EXIT_SUCCESS;
}</syntaxhighlight>
{{out}}
<pre>Factors of 3135 are: 1 3 5 11 15 19 33 55 57 95 165 209 285 627 1045 3135
Factors of 45 are: 1 3 5 9 15 45
Factors of 60 are: 1 2 3 4 5 6 10 12 15 20 30 60
Factors of 81 are: 1 3 9 27 81 </pre>
=={{header|Ceylon}}==
<syntaxhighlight lang="ceylon">shared void run() {
{Integer*} getFactors(Integer n) =>
(1..n).filter((Integer element) => element.divides(n));
for(Integer i in 1..100) {
print("the factors of ``i`` are ``getFactors(i)``");
}
}</syntaxhighlight>
=={{header|Chapel}}==
Inspired by the Clojure solution:
<
for i in 1..floor(sqrt(n)):int {
if n % i == 0 then {
Line 672 ⟶ 2,276:
}
}
}</
=={{header|Clojure}}==
<
(filter #(zero? (rem n %)) (range 1 (inc n))))
(print (factors 45))</
(1 3 5 9 15 45)
Improved version. Considers small factors from 1 up to (sqrt n) -- we increment it because range does not include the end point. Pair each small factor with its co-factor, flattening the results, and put them into a sorted set to get the factors in order.
<
(into (sorted-set)
(mapcat (fn [x] [x (/ n x)])
(filter #(zero? (rem n %)) (range 1 (inc (Math/sqrt n)))) )))</
Same idea, using for comprehensions.
<
(into (sorted-set)
(reduce concat
(for [x (range 1 (inc (Math/sqrt n))) :when (zero? (rem n x))]
[x (/ n x)]))))</
=={{header|CLU}}==
{{trans|Sather}}
<syntaxhighlight lang="clu">isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0=0 then return(s) end
x1: int := (x0 + s/x0)/2
while x1<x0 do
x0, x1 := x1, (x1 + s/x1)/2
end
return(x0)
end isqrt
factors = iter (n: int) yields (int)
yield(1)
for i: int in int$from_to(2,isqrt(n)) do
if n//i=0 then
yield(i)
if i*i ~= n then yield(n/i) end
end
end
yield(n)
end factors
start_up = proc ()
po: stream := stream$primary_output()
a: array[int] := array[int]$[3135, 45, 64, 53, 45, 81]
for n: int in array[int]$elements(a) do
stream$puts(po, "Factors of " || int$unparse(n) || ":")
for f: int in factors(n) do
stream$puts(po, " " || int$unparse(f))
end
stream$putl(po, "")
end
end start_up</syntaxhighlight>
{{out}}
<pre>Factors of 3135: 1 3 1045 5 627 11 285 15 209 19 165 33 95 55 57 3135
Factors of 45: 1 3 15 5 9 45
Factors of 64: 1 2 32 4 16 8 64
Factors of 53: 1 53
Factors of 45: 1 3 15 5 9 45
Factors of 81: 1 3 27 9 81</pre>
=={{header|COBOL}}==
<syntaxhighlight lang="cobol">
IDENTIFICATION DIVISION.
PROGRAM-ID. FACTORS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 CALCULATING.
03 NUM USAGE BINARY-LONG VALUE ZERO.
03 LIM USAGE BINARY-LONG VALUE ZERO.
03 CNT USAGE BINARY-LONG VALUE ZERO.
03 DIV USAGE BINARY-LONG VALUE ZERO.
03 REM USAGE BINARY-LONG VALUE ZERO.
03 ZRS USAGE BINARY-SHORT VALUE ZERO.
01 DISPLAYING.
03 DIS PIC 9(10) USAGE DISPLAY.
PROCEDURE DIVISION.
MAIN-PROCEDURE.
DISPLAY "Factors of? " WITH NO ADVANCING
ACCEPT NUM
DIVIDE NUM BY 2 GIVING LIM.
PERFORM VARYING CNT FROM 1 BY 1 UNTIL CNT > LIM
DIVIDE NUM BY CNT GIVING DIV REMAINDER REM
IF REM = 0
MOVE CNT TO DIS
PERFORM SHODIS
END-IF
END-PERFORM.
MOVE NUM TO DIS.
PERFORM SHODIS.
STOP RUN.
SHODIS.
MOVE ZERO TO ZRS.
INSPECT DIS TALLYING ZRS FOR LEADING ZERO.
DISPLAY DIS(ZRS + 1:)
EXIT PARAGRAPH.
END PROGRAM FACTORS.
</syntaxhighlight>
=={{header|CoffeeScript}}==
<
# robust--we'll use it to verify the more complicated (but hopefully faster)
# algorithm.
Line 753 ⟶ 2,443:
console.log n, factors
if n < 1000000
verify_factors factors, n</
{{out}}
<pre>> coffee factors.coffee
1 [ 1 ]
3 [ 1, 3 ]
Line 775 ⟶ 2,466:
11111111111,
33333333333,
99999999999 ]</
=={{header|Common Lisp}}==
We iterate in the range <code>1..sqrt(n)</code> collecting ‘low’ factors and corresponding ‘high’ factors, and combine at the end to produce an ordered list of factors.
<
(do ((limit (1+ (isqrt n))) (factor 1 (1+ factor)))
((= factor limit)
(when (= n (* limit limit))
(push limit highs))
(remove-duplicates (nreconc lows highs)))
(multiple-value-bind (quotient remainder) (floor n factor)
(when (zerop remainder)
(push factor lows)
(push quotient highs)))))</
=={{header|Crystal}}==
{{trans|Ruby}}
Brute force and slow, by checking every value up to n.
<syntaxhighlight lang="ruby">struct Int
def factors() (1..self).select { |n| (self % n).zero? } end
end</syntaxhighlight>
Faster, by only checking values up to <math>\sqrt{n}</math>.
<syntaxhighlight lang="ruby">struct Int
def factors
f = [] of Int32
(1..Math.sqrt(self)).each{ |i|
(f << i; f << self // i if self // i != i) if (self % i).zero?
}
f.sort
end
end</syntaxhighlight>
'''Tests:'''
<syntaxhighlight lang="ruby">
[45, 53, 64].each {|n| puts "#{n} : #{n.factors}"}</syntaxhighlight>
{{out}}
<pre>
45 : [1, 3, 5, 9, 15, 45]
53 : [1, 53]
64 : [1, 2, 4, 8, 16, 32, 64]</pre>
=={{header|D}}==
===Procedural Style===
<
T[] factors(T)(in T n) pure nothrow {
Line 814 ⟶ 2,532:
void main() {
writefln("%(%s\n%)", [45, 53, 64, 1111111].map!factors);
}</
{{out}}
<pre>[1, 3, 5, 9, 15, 45]
Line 822 ⟶ 2,540:
===Functional Style===
<
auto factors(I)(I n) {
Line 830 ⟶ 2,548:
void main() {
36.factors.writeln;
}</
{{out}}
<pre>[1, 2, 3, 4, 6, 9, 12, 18, 36]</pre>
=={{header|Dart}}==
<pre>
import 'dart:math';
factors(n)
{
var factorsArr = [];
factorsArr.add(n);
factorsArr.add(1);
for(var test = n - 1; test >= sqrt(n).toInt(); test--)
if(n % test == 0)
{
factorsArr.add(test);
factorsArr.add(n / test);
}
return factorsArr;
}
void main() {
print(factors(5688));
}
</pre>
=={{header|Dc}}==
=== Simple O(n) version ===
<syntaxhighlight lang="dc">
[Enter positive number: ]P ? sn
[Factors of ]P lnn [ are: ]P
[q]sq 1si [[ ]P lin]sp [ li ln <q ln li % 0=p li1+si lxx ]dsxx AP
</syntaxhighlight>
{{out}}
Factors of 998877 are: 1 3 11 33 30269 90807 332959 998877
0m1.120s
=== Faster O(sqrt(n)) version ===
<syntaxhighlight lang="dc">
[Enter positive number: ]P ? sn
[Factors of ]P lnn [ are: ]P
[q]sq lnvsv 1si 0sj [[ ]P lin]sp [lkSb lj1+sj]sa [lpx ln li /dsk li<a ]sP
[li lv <q ln li % 0=P li1+si lxx]dsxx
[lj 1>q lj1-sj Lbsi lpx lxx]dsxx AP
</syntaxhighlight>
0m0.004s
=={{header|Delphi}}==
See [[#Pascal]].
=={{header|Dyalect}}==
<syntaxhighlight lang="dyalect">func Iterator.Where(pred) {
for x in this when pred(x) {
yield x
}
}
func Integer.Factors() {
(1..this).Where(x => this % x == 0)
}
for x in 45.Factors() {
print(x)
}</syntaxhighlight>
Output:
<pre>1
3
5
9
15
45</pre>
=={{header|E}}==
{{improve|E|Use a cleverer algorithm such as in the Common Lisp example.}}
<
var xfactors := []
for f ? (x % f <=> 0) in 1..x {
Line 842 ⟶ 2,629:
}
return xfactors
}</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">n = 720
for i = 1 to n
if n mod i = 0
factors[] &= i
.
.
print factors[]</syntaxhighlight>
=={{header|EchoLisp}}==
'''prime-factors''' gives the list of n's prime-factors. We mix them to get all the factors.
<syntaxhighlight lang="scheme">
;; ppows
;; input : a list g of grouped prime factors ( 3 3 3 ..)
;; returns (1 3 9 27 ...)
(define (ppows g (mult 1))
(for/fold (ppows '(1)) ((a g))
(set! mult (* mult a))
(cons mult ppows)))
;; factors
;; decomp n into ((2 2 ..) ( 3 3 ..) ) prime factors groups
;; combines (1 2 4 8 ..) (1 3 9 ..) lists
(define (factors n)
(list-sort <
(if (<= n 1) '(1)
(for/fold (divs'(1)) ((g (map ppows (group (prime-factors n)))))
(for*/list ((a divs) (b g)) (* a b))))))
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="scheme">
(lib 'bigint)
(factors 666)
→ (1 2 3 6 9 18 37 74 111 222 333 666)
(length (factors 108233175859200))
→ 666 ;; 💀
(define huge 1200034005600070000008900000000000000000)
(time ( length (factors huge)))
→ (394ms 7776)
</syntaxhighlight>
=={{header|EDSAC order code}}==
Input is limited to 10 decimal digits, which is as many as the EDSAC print subroutine P7 can handle. Factors are printed in pairs, such that the product of the factors in each pair equals the input number.
2021-10-10 Integers are now read from the tape in decimal format, instead of being defined by the awkward method of pseudo-orders. The factorization of 999,999,999 has been removed, as it took too long on the commonly-used EdsacPC simulator (14.6 million orders - over 6 hours on the original EDSAC).
<syntaxhighlight lang="edsac">
[Factors of an integer, from Rosetta Code website.]
[EDSAC program, Initial Orders 2.]
[The numbers to be factorized are read in by library subroutine R2
(Wilkes, Wheeler and Gill, 1951 edition, pp.96-97, 148).]
[The address of the integers is placed in location 46, so they can be
referred to by the N parameter (or we could have used 45 and H, etc.)]
T 46 K
P 600 F [address of integers]
[Subroutine R2]
GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z
T #N [pass address of integers to R2]
[List of integers to be factorized; edit ad lib. R2 requires 'F' after
each integer except the last, and '#' (pi) after the last.
This program uses 0 to mark the end of the list.]
42000F999999F0#
T Z [resume normal loading]
[Modified library subroutine P7.]
[Prints signed integer; up to 10 digits, left-justified.]
[Input: 0D = integer,]
[54 locations. Load at even address. Workspace 4D.]
T 56 K
GKA3FT42@A49@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@
TFH17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@
T31@A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFSFL8FT4DE39@
[Division subroutine for positive long integers.
35-bit dividend and divisor (max 2^34 - 1)
returning quotient and remainder.
Input: dividend at 4D, divisor at 6D
Output: remainder at 4D, quotient at 6D.
37 locations; working locations 0D, 8D.]
T 110 K
GKA3FT35@A6DU8DTDA4DRDSDG13@T36@ADLDE4@T36@T6DA4DSDG23@
T4DA6DYFYFT6DT36@A8DSDE35@T36@ADRDTDA6DLDT6DE15@EFPF
[********************** ROSETTA CODE TASK **********************]
[Subroutine to find and print factors of a positive integer.
Input: 0D = integer, maximum 10 decimal digits.
Load at even address.]
T 148 K
G K
A 3 F [form and plant link for return]
T 55 @
A D [load integer whose factors are to be found]
T 56#@ [store]
A 62#@ [load 1]
T 58#@ [possible factor := 1]
S 65 @ [negative count of items per line]
T 64 @ [initialize count]
[Start of loop round possible factors]
[8] T F [clear acc]
A 56#@ [load integer]
T 4 D [to 4F for division]
A 58#@ [load possible factor]
T 6 D [to 6F for division]
A 13 @ [for return from next]
G 110 F [do division; clears acc]
A 6 D [save quotient (6F may be changed below)]
T 60#@
S 4 D [load negative of remainder]
G 44 @ [skip if remainder > 0]
[Here if m is a factor of n.]
[Print m and the quotient together]
T F [clear acc]
A 64 @ [test count of items per line]
G 26 @ [skip if not start of line]
S 65 @ [start of line, reset count]
T 64 @
O 70 @ [and print CR, LF]
O 71 @
[26] T F [clear acc]
O 67 @ [print '(']
A 58#@ [load factor]
T D [to 0D for printing]
A 30 @ [for return from next]
G 56 F [print factor; clears acc]
O 69 @ [print comma]
A 60#@ [load quotient]
T D [to 0D for printing]
A 35 @ [for return from next]
G 56 F [print quotient; clears acc]
O 68 @ [print ')']
A 64 @ [negative counter for items per line]
A 2 F [inc]
E 43 @ [skip if end of line]
O 66 @ [not end of line, print 2 spaces]
O 66 @
[43] T 64 @ [update counter]
[Common code after testing possible factor]
[44] T F [clear acc]
A 58#@ [load possible factor]
A 62#@ [inc by 1]
U 58#@ [store back]
S 60#@ [compare with quotient]
G 8 @ [loop if (new factor) < (old quotient)]
[Here when found all factors]
O 70 @ [print CR, LF twice]
O 71 @
O 70 @
O 71 @
T F [exit with acc = 0]
[55] E F [return]
[--------]
[56] PF PF [number whose factors are to be found]
[58] PF PF [possible factor]
[60] PF PF [integer part of (number/factor)]
T62#Z PF [clear sandwich digit in 35-bit constant 1]
T 62 Z [resume normal loading]
[62] PD PF [35-bit constant 1]
[64] P F [negative counter for items per line]
[65] P 4 F [items per line, in address field]
[66] ! F [space]
[67] K F [left parenthesis (in figures mode)]
[68] L F [right parenthesis (in figures mode)]
[69] N F [comma (in figures mode)]
[70] @ F [carriage return]
[71] & F [line feed]
[Main routine for demonstrating subroutine.]
T 400 K
G K
[0] # F [set figures mode]
[1] K 4096 F [null char]
[2] S #N [order to load negative of first number]
[3] P 2 F [to inc address by 2 for next number]
[Enter with acc = 0]
[4] O @ [set teleprinter to figures]
A 2 @ [load order for first integer]
[6] T 7 @ [plant in next order]
[7] S D [load negative of 35-bit integer]
E 17 @ [exit if number is 0]
T D [negative to 0D]
S D [convert to positive]
T D [pass to subroutine]
A 12 @ [call subroutine to find and print factors]
G 148 F
A 7 @ [modify order above, for next integer]
A 3 @
E 6 @ [always jump, since S = 12 > 0]
[--------]
[17] O 1 @ [done, print null to flush printer buffer]
Z F [stop]
E 4 Z [define entry point]
P F [acc = 0 on entry]
</syntaxhighlight>
{{out}}
<pre>
(1,42000) (2,21000) (3,14000) (4,10500)
(5,8400) (6,7000) (7,6000) (8,5250)
(10,4200) (12,3500) (14,3000) (15,2800)
(16,2625) (20,2100) (21,2000) (24,1750)
(25,1680) (28,1500) (30,1400) (35,1200)
(40,1050) (42,1000) (48,875) (50,840)
(56,750) (60,700) (70,600) (75,560)
(80,525) (84,500) (100,420) (105,400)
(112,375) (120,350) (125,336) (140,300)
(150,280) (168,250) (175,240) (200,210)
(1,999999) (3,333333) (7,142857) (9,111111)
(11,90909) (13,76923) (21,47619) (27,37037)
(33,30303) (37,27027) (39,25641) (63,15873)
(77,12987) (91,10989) (99,10101) (111,9009)
(117,8547) (143,6993) (189,5291) (231,4329)
(259,3861) (273,3663) (297,3367) (333,3003)
(351,2849) (407,2457) (429,2331) (481,2079)
(693,1443) (777,1287) (819,1221) (999,1001)
</pre>
=={{header|Ela}}==
===Using higher-order function===
<
factors m = filter (\x -> m % x == 0) [1..m]</
===Using comprehension===
<
=={{header|Elixir}}==
<syntaxhighlight lang="elixir">defmodule RC do
def factor(1), do: [1]
def factor(n) do
(for i <- 1..div(n,2), rem(n,i)==0, do: i) ++ [n]
end
# Recursive (faster version);
def divisor(n), do: divisor(n, 1, []) |> Enum.sort
defp divisor(n, i, factors) when n < i*i , do: factors
defp divisor(n, i, factors) when n == i*i , do: [i | factors]
defp divisor(n, i, factors) when rem(n,i)==0, do: divisor(n, i+1, [i, div(n,i) | factors])
defp divisor(n, i, factors) , do: divisor(n, i+1, factors)
end
Enum.each([45, 53, 60, 64], fn n ->
IO.puts "#{n}: #{inspect RC.factor(n)}"
end)
IO.puts "\nRange: #{inspect range = 1..10000}"
funs = [ factor: &RC.factor/1,
divisor: &RC.divisor/1 ]
Enum.each(funs, fn {name, fun} ->
{time, value} = :timer.tc(fn -> Enum.count(range, &length(fun.(&1))==2) end)
IO.puts "#{name}\t prime count : #{value},\t#{time/1000000} sec"
end)
</syntaxhighlight>
{{out}}
<pre>
45: [1, 3, 5, 9, 15, 45]
53: [1, 53]
60: [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
64: [1, 2, 4, 8, 16, 32, 64]
Range: 1..10000
factor prime count : 1229, 7.316 sec
divisor prime count : 1229, 0.265 sec
</pre>
=={{header|EMal}}==
<syntaxhighlight lang="emal">
fun factors = List by int n
List result = int[1]
for each int i in range(2, n)
if n % i == 0 do result.append(i) end
end
result.append(n)
return result
end
fun main = int by List args
int n = when(args.length == 0, ask(int, "Enter the number to factor please "), int!args[0])
writeLine(factors(n))
return 0
end
exit main(Runtime.args)
</syntaxhighlight>
{{out}}
<pre>
emal.exe Org\RosettaCode\FactorsOfAnInteger.emal 999997
[1,757,1321,999997]
</pre>
=={{header|Erlang}}==
===with Built in fuctions===
<syntaxhighlight lang="erlang">factors(N) ->
[I || I <- lists:seq(1,trunc(N/2)), N rem I == 0]++[N].</syntaxhighlight>
===Recursive===
Another, less concise, but faster version
<syntaxhighlight lang="erlang">
-module(divs).
-export([divs/1]).
divs(0) -> [];
divs(1) -> [];
divs(N) -> lists:sort(divisors(1,N))++[N].
divisors(1,N) ->
[1] ++ divisors(2,N,math:sqrt(N)).
divisors(K,_N,Q) when K > Q -> [];
divisors(K,N,_Q) when N rem K =/= 0 ->
[] ++ divisors(K+1,N,math:sqrt(N));
divisors(K,N,_Q) when K * K == N ->
[K] ++ divisors(K+1,N,math:sqrt(N));
divisors(K,N,_Q) ->
[K, N div K] ++ divisors(K+1,N,math:sqrt(N)).
</syntaxhighlight>
{{out}}
<pre>
58> timer:tc(divs, factors, [20000]).
{2237,
[1,2,4,5,8,10,16,20,25,32,40,50,80,100,125,160,200,250,400,
500,625,800,1000,1250,2000,2500,4000|...]}
59> timer:tc(divs, divs, [20000]).
{106,
[1,2,4,5,8,10,16,20,25,32,40,50,80,100,125,160,200,250,400,
500,625,800,1000,1250,2000,2500,4000|...]}
</pre>
The first number is milliseconds. I'v ommitted repeating the first fuction.
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM FACTORS
!$DOUBLE
PROCEDURE FACTORLIST(N->L$)
LOCAL C%,I,FLIPS%,I%
LOCAL DIM L[32]
FOR I=1 TO SQR(N) DO
IF N=I*INT(N/I) THEN
L[C%]=I
C%=C%+1
IF N<>I*I THEN
L[C%]=INT(N/I)
C%=C%+1
END IF
END IF
END FOR
! BUBBLE SORT ARRAY L[]
FLIPS%=1
WHILE FLIPS%>0 DO
FLIPS%=0
FOR I%=0 TO C%-2 DO
IF L[I%]>L[I%+1] THEN SWAP(L[I%],L[I%+1]) FLIPS%=1
END FOR
END WHILE
L$=""
FOR I%=0 TO C%-1 DO
L$=L$+STR$(L[I%])+","
END FOR
L$=LEFT$(L$,LEN(L$)-1)
END PROCEDURE
BEGIN
PRINT(CHR$(12);) ! CLS
FACTORLIST(45->L$)
PRINT("The factors of 45 are ";L$)
FACTORLIST(12345->L$)
PRINT("The factors of 12345 are ";L$)
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
The factors of 45 are 1, 3, 5, 9, 15, 45
The factors of 12345 are 1, 3, 5, 15, 823, 2469, 4115, 12345
</pre>
=={{header|Excel}}==
===LAMBDA===
Binding the name '''FACTORS''' to a custom function defined by the following LAMBDA expression
in the Name Manager of an Excel workbook.
(See: [https://www.microsoft.com/en-us/research/blog/lambda-the-ultimatae-excel-worksheet-function/ The LAMBDA worksheet function in Excel])
{{Works with|Office 365 Betas 2021}}
<syntaxhighlight lang="lisp">=LAMBDA(n,
IF(1 < n,
LET(
froot, SQRT(n),
nroot, FLOOR.MATH(froot),
lows, FILTERP(
LAMBDA(x, 0 = MOD(n, x))
)(
ENUMFROMTO(1)(nroot)
),
APPEND(lows)(
LAMBDA(x, n / x)(
REVERSE(
IF(froot <> nroot,
lows,
INIT(lows)
)
)
)
)
),
IF(1 = n, {1}, NA())
)
)</syntaxhighlight>
and assuming that in the same worksheet, each of the following names is bound to the reusable generic lambda expression which follows it:
<syntaxhighlight lang="lisp">APPEND
=LAMBDA(xs,
LAMBDA(ys,
LET(
nx, ROWS(xs),
rowIndexes, SEQUENCE(nx + ROWS(ys)),
colIndexes, SEQUENCE(
1,
MAX(COLUMNS(xs), COLUMNS(ys))
),
IF(
rowIndexes <= nx,
INDEX(xs, rowIndexes, colIndexes),
INDEX(ys, rowIndexes - nx, colIndexes)
)
)
)
)
ENUMFROMTO
=LAMBDA(a,
LAMBDA(z,
SEQUENCE(1 + z - a, 1, a, 1)
)
)
FILTERP
=LAMBDA(p,
LAMBDA(xs,
FILTER(xs, p(xs))
)
)
INIT
=LAMBDA(xs,
IF(
AND(1=ROWS(xs), ISBLANK(xs)),
NA(),
INDEX(
xs,
SEQUENCE(ROWS(xs)-1, 1, 1, 1)
)
)
)
REVERSE
=LAMBDA(xs,
LET(
n, ROWS(xs),
SORTBY(
xs,
SEQUENCE(n, 1, n, -1)
)
)
)</syntaxhighlight>
The '''FACTORS''' function, applied to an integer, defines a column of integer values.
Here we define a row instead, by composing '''FACTORS''' with the standard '''TRANSPOSE''' function.
{{Out}}
{| class="wikitable"
|-
|||style="text-align:right; font-family:serif; font-style:italic; font-size:120%;"|fx
! colspan="17" style="text-align:left; vertical-align: bottom; font-family:Arial, Helvetica, sans-serif !important;"|=TRANSPOSE(FACTORS(A2))
|- style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff;"
|
| A
| B
| C
| D
| E
| F
| G
| H
| I
| J
| K
| L
| M
| N
| O
| P
| Q
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 1
| style="text-align:right; font-weight:bold" | N
| style="font-weight:bold" | Factors
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
| style="font-weight:bold" |
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 2
| style="text-align:right; font-weight:bold" | 64
| style="background-color:#cbcefb;" | 1
| 2
| 4
| 8
| 16
| 32
| 64
|
|
|
|
|
|
|
|
|
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 3
| style="text-align:right; font-weight:bold" | 120
| 1
| 2
| 3
| 4
| 5
| 6
| 8
| 10
| 12
| 15
| 20
| 24
| 30
| 40
| 60
| 120
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 4
| style="text-align:right; font-weight:bold" | 123456789
| 1
| 3
| 9
| 3607
| 3803
| 10821
| 11409
| 32463
| 34227
| 13717421
| 41152263
| 123456789
|
|
|
|
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 5
| style="text-align:right; font-weight:bold" | 2
| 1
| 2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 6
| style="text-align:right; font-weight:bold" | 1
| 1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 7
| style="text-align:right; font-weight:bold" | 0
| #N/A
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 8
| style="text-align:right; font-weight:bold" | -1
| #N/A
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|}
=={{header|F Sharp|F#}}==
Line 864 ⟶ 3,310:
Also, this is lazily evaluated.
<
for divisor in 1 .. (float >> sqrt >> int) number do
if number % divisor = 0 then
yield divisor
if number <> 1 then yield number / divisor //special case condition: when number=1 then divisor=(number/divisor), so don't repeat it
}</
===Prime factoring===
<syntaxhighlight lang="fsharp">
[6;120;2048;402642;1206432] |> Seq.iter(fun n->printf "%d :" n; [1..n]|>Seq.filter(fun g->n%g=0)|>Seq.iter(fun n->printf " %d" n); printfn "");;</syntaxhighlight>
{{out}}
<pre>
OUTPUT :
6 : 1 2 3 6
120 : 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
2048 : 1 2 4 8 16 32 64 128 256 512 1024 2048
402642 : 1 2 3 6 9 18 22369 44738 67107 134214 201321 402642
120643200 : 1 2 3 4 6 8 9 12 16 18 24 32 36 48 59 71 72 96 118 142 144 177 213 236 284 288 354 426 472 531 568 639 708 852 944 1062 1136 12
78 1416 1704 1888 2124 2272 2556 2832 3408 4189 4248 5112 5664 6816 8378 8496 10224 12567 16756 16992 20448 25134 33512 37701 50268 67024 75402 10053
6 134048 150804 201072 301608 402144 603216 1206432
</pre>
=={{header|Factor}}==
USE: math.primes.factors
( scratchpad ) 24 divisors .
Line 877 ⟶ 3,339:
=={{header|FALSE}}==
<
45f;! 53f;! 64f;!</
=={{
<syntaxhighlight lang="fish">0v
>i:0(?v'0'%+a*
>~a,:1:>r{% ?vr:nr','ov
^:&:;?(&:+1r:< <
</syntaxhighlight>
Must be called with pre-polulated value (Positive Integer) in the input stack. Try at Fish Playground[https://fishlanguage.com/playground/onD7KN6YK3XMzLFdr].
For Input Number : <pre> 120</pre>
The following output was generated:
<pre>1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120,</pre>
=={{header|Forth}}==
This is a slightly optimized algorithm, since it realizes there are no factors between n/2 and n. The values are saved on the stack and - in true Forth fashion - printed in descending order.
<
: .factors factors begin dup dup . 1 <> while drop repeat drop cr ;
Line 888 ⟶ 3,361:
53 .factors
64 .factors
100 .factors</
=== Alternative version with vectored execution ===
It's not really idiomatic FORTH to leave a variable number of items on the stack, so instead this version repeatedly calls an execution token for each factor, and it uses a defining word to create a fold over the factors of an integer. This version also only tests up to the square root, which means that items are generated in pairs, rather than in sorted order.
<syntaxhighlight lang="forth">
: sq s" dup *" evaluate ; immediate
: factors ( n a xt -- )
swap 2>r 1
BEGIN 2dup sq > WHILE
2dup /mod swap 0= IF
over
r> r@ execute
r@ execute >r
ELSE
drop
THEN 1+
REPEAT
2dup sq = IF
2r> swap execute nip
ELSE
2drop r> rdrop
THEN ;
: <with-factors>
create 2, does> 2@ factors ;
0 :noname nip 1+ ; <with-factors> count-factors
0 ' + <with-factors> sum-factors
0 :noname swap . ; <with-factors> (.factors)
: .factors (.factors) drop ;
</syntaxhighlight>
{{Out}}
<pre>
100 .factors 1 100 2 50 4 25 5 20 10 ok
100 count-factors . 9 ok
100 sum-factors . 217 ok
1 100 + 2 + 50 + 4 + 25 + 5 + 20 + 10 + . 217 ok \ test sum-factors result
77 .factors 1 77 7 11 ok
108 .factors 1 108 2 54 3 36 4 27 6 18 9 12 ok
</pre>
=={{
{{works with|Fortran|90 and later}}
<
implicit none
integer :: i, number
Line 911 ⟶ 3,424:
end if
end program</
=={{
Frink has built-in factoring functions which use wheel factoring, trial division, Pollard p-1 factoring, and Pollard rho factoring. It also recognizes some special forms (e.g. Mersenne numbers) and handles them efficiently. Integers can either be decomposed into prime factors or all factors.
Line 922 ⟶ 3,435:
The following produces all factors of n, including 1 and n:
<syntaxhighlight lang
=={{header|FunL}}==
Function to compute set of factors:
<
Test:
<
println( 'The set of factors of ' + x + ' is ' + factors(x) )</
{{out}}
Line 943 ⟶ 3,456:
=={{header|GAP}}==
<
DivisorsInt(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]
Line 962 ⟶ 3,475:
div2(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]</
=={{header|Go}}==
Trial division, no prime number generator, but with some optimizations. It's good enough to factor any 64 bit integer, with large primes taking several seconds.
<
import "fmt"
Line 1,017 ⟶ 3,530:
fmt.Println(fs)
fmt.Println("Number of factors =", len(fs))
}</
{{out}}
<pre>Factors of -1 not computed
Line 1,047 ⟶ 3,561:
Number of factors = 2</pre>
=={{
<syntaxhighlight lang="gosu">var numbers = {11, 21, 32, 45, 67, 96}
numbers.each(\ number -> printFactors(number))
function printFactors(n: int) {
if (n < 1) return
var result ="${n} => "
(1 .. n/2).each(\ i -> {result += n % i == 0 ? "${i} " : ""})
print("${result}${n}")
}</syntaxhighlight>
{{out}}
<pre>
11 => 1 11
21 => 1 3 7 21
32 => 1 2 4 8 16 32
45 => 1 3 5 9 15 45
67 => 1 67
96 => 1 2 3 4 6 8 12 16 24 32 48 96
</pre>
=={{header|Groovy}}==
A straight brute force approach up to the square root of ''N'':
<
if (target == 1) return [1L]
Line 1,061 ⟶ 3,596:
[1] + lowfactors + (0..<nhalf).collect { target.intdiv(lowfactors[it]) }.reverse() + [target]
}</
Test:
<
{{out}}
<pre>[number:1, factors:[1]]
[number:2, factors:[1, 2]]
Line 1,098 ⟶ 3,633:
[number:333333, factors:[1, 3, 7, 9, 11, 13, 21, 33, 37, 39, 63, 77, 91, 99, 111, 117, 143, 231, 259, 273, 333, 407, 429, 481, 693, 777, 819, 1001, 1221, 1287, 1443, 2331, 2849, 3003, 3367, 3663, 4329, 5291, 8547, 9009, 10101, 15873, 25641, 30303, 37037, 47619, 111111, 333333]]</pre>
=={{
Using
<
import
import Data.List (product)
-- primePowerFactors :: Integer -> [(Integer,Int)]
factors = map product .
mapM (\(p,m)-> [p^i | i<-[0..m]]) . primePowerFactors</syntaxhighlight>
Returns list of factors out of order, e.g.:
<syntaxhighlight lang="haskell">~> factors 42
[1,7,3,21,2,14,6,42]</syntaxhighlight>
Or, [[Prime_decomposition#Haskell|prime decomposition task]] can be used (although, a trial division-only version will become very slow for large primes),
<syntaxhighlight lang="haskell">import Data.List (group)
primePowerFactors = map (\x-> (head x, length x)) . group . factorize</syntaxhighlight>
The above function can also be found in the package [http://hackage.haskell.org/package/arithmoi <code>arithmoi</code>], as <code>Math.NumberTheory.Primes.factorise :: Integer -> [(Integer, Int)]</code>, [http://hackage.haskell.org/package/arithmoi-0.4.2.0/docs/Math-NumberTheory-Primes-Factorisation.html which performs] "factorisation of Integers by the elliptic curve algorithm after Montgomery" and "is best suited for numbers of up to 50-60 digits".
Or, deriving cofactors from factors up to the square root:
<syntaxhighlight lang="haskell">integerFactors :: Int -> [Int]
integerFactors n
| 1 > n = []
| otherwise = lows <> (quot n <$> part n (reverse lows))
where
part n
| n == square = tail
| otherwise = id
(square, lows) =
(,) . (^ 2)
<*> (filter ((0 ==) . rem n) . enumFromTo 1)
$ floor (sqrt $ fromIntegral n)
main :: IO ()
main = print $ integerFactors 600</syntaxhighlight>
{{Out}}
<pre>[1,2,3,4,5,6,8,10,12,15,20,24,25,30,40,50,60,75,100,120,150,200,300,600]</pre>
=== List comprehension ===
Naive, functional, no import, in increasing order:
<syntaxhighlight lang="haskell">factorsNaive n =
[ i
| i <- [1 .. n]
, mod n i == 0 ]</syntaxhighlight>
<syntaxhighlight lang="haskell">~> factorsNaive 25
[1,5,25]</syntaxhighlight>
Factor, ''cofactor''.
<
factorsCo n =
sort
[ i
, (d, 0) <- [divMod n i]
, i <-
i :
[ d
| d > i ] ]</syntaxhighlight>
A version of the above without the need for sorting, making it to be ''online'' (i.e. productive immediately, which can be seen in GHCi); factors in increasing order:
<syntaxhighlight lang="haskell">factorsO n =
ds ++
[ r
| (d, 0) <- [divMod n r]
, r <-
r :
[ d
| d > r ] ] ++
reverse (map (n `div`) ds)
where
r = floor (sqrt (fromIntegral n))
ds =
[ i
| i <- [1 .. r - 1]
, mod n i == 0 ]</syntaxhighlight>
Testing:
<syntaxhighlight lang="haskell">*Main> :set +s
~> factorsO 120
[1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120]
(0.
~> factorsO 12041111117
[1,7,41,287,541,3787,22181,77551,155267,542857,3179591,22257137,41955091,2936856
37,1720158731,12041111117]
(0.09 secs, 50758224 bytes)</syntaxhighlight>
=={{header|HicEst}}==
<
DO i = 1, N^0.5
Line 1,143 ⟶ 3,732:
ENDDO
END</
=={{header|Icon}} and {{header|Unicon}}==
<
numbers := arglist ||| [ 32767, 45, 53, 64, 100] # combine command line provided and default set of values
every writes(lf,"factors of ",i := !numbers,"=") & writes(divisors(i)," ") do lf := "\n"
end
link factors</
{{out}}
<pre>factors of 32767=1 7 31 151 217 1057 4681 32767
factors of 45=1 3 5 9 15 45
Line 1,160 ⟶ 3,750:
{{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/src/procs/factors.icn divisors]
=={{Header|Insitux}}==
{{Trans|Clojure}}
<syntaxhighlight lang="insitux">
(function factors n
(filter (div? n) (range 1 (inc n))))
(factors 45)
</syntaxhighlight>
{{out}}
<pre>
[1 3 5 9 15 45]
</pre>
=={{header|J}}==
The "brute force" approach is the most concise:
<syntaxhighlight lang="j">foi=: [: I. 0 = (|~ i.@>:)</syntaxhighlight>
Example use:
<syntaxhighlight lang="j"> foi 40
1 2 4 5 8 10 20 40</syntaxhighlight>
Basically we test every non-negative integer up through the number itself to see if it divides evenly.
However, this becomes very slow for large numbers. So other approaches can be worthwhile.
J has a primitive, q: which returns its argument's prime factors.
<syntaxhighlight lang="j">q: 40
2 2 2 5</syntaxhighlight>
Alternatively, q: can produce provide a table of the exponents of the unique relevant prime factors
<
2 3 5 7
2 1 1 1</
With this, we can form lists of each of the potential relevant powers of each of these prime factors
<
┌─────┬───┬───┬───┐
│1 2 4│1 3│1 5│1 7│
└─────┴───┴───┴───┘</
From here, it's a simple matter (<code>*/&>@{</code> or, find all possible combinations of one item from each list (<code>{</code> without a left argument) then unpack each list and multiply its elements) to compute all possible factors of the original number
<
factrs 40
1 5
2 10
4 20
8 40</
However, a data structure which is organized around the prime decomposition of the argument can be hard to read. So, for reader convenience, we should probably arrange them in a monotonically increasing list:
<
1 2 3 4 5 6 7 10 12 14 15 20 21 28 30 35 42 60 70 84 105 140 210 420</
A less efficient, but concise variation on this theme:
<
1 5 2 10 4 20 8 40</
This computes 2^n intermediate values where n is the number of prime factors of the original number.
That said, note that we get a representation issue when dealing with large numbers:
<syntaxhighlight lang="j"> factors 568474220
1 2 4 5 10 17 20 34 68 85 170 340 1.67198e6 3.34397e6 6.68793e6 8.35992e6 1.67198e7 2.84237e7 3.34397e7 5.68474e7 1.13695e8 1.42119e8 2.84237e8 5.68474e8</syntaxhighlight>
One approach here (if we don't want to explicitly format the result) is to use an arbitrary precision (aka "extended") argument. This propagates through into the result:
<syntaxhighlight lang="j"> factors 568474220x
1 2 4 5 10 17 20 34 68 85 170 340 1671983 3343966 6687932 8359915 16719830 28423711 33439660 56847422 113694844 142118555 284237110 568474220</syntaxhighlight>
Another less efficient approach, in which remainders are examined up to the square root, larger factors obtained as fractions, and the combined list nubbed and sorted might be:
<
Y=. y"_
/:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y
Line 1,205 ⟶ 3,835:
factorsOfNumber 40
1 2 4 5 8 10 20 40</
Another approach:
<
factors=: (*/@:^"1 odometer@:>:)/@q:~&__</
See also the J essays [[j:Essays/Odometer|Odometer]] and [[j:Essays/Divisors|Divisors]].
=={{header|Java}}==
{{works with|Java|5+}}
<
{
TreeSet<Long> factors = new TreeSet<Long>();
Line 1,228 ⟶ 3,858:
}
return factors;
}</
=={{header|JavaScript}}==
===Imperative===
<syntaxhighlight lang="javascript">function factors(num)
{
var
Line 1,250 ⟶ 3,883:
factors(45); // [1,3,5,9,15,45]
factors(53); // [1,53]
factors(64); // [1,2,4,8,16,32,64]</
===Functional===
====ES5====
Translating the naive list comprehension example from Haskell, using a list monad for the comprehension
<syntaxhighlight lang="javascript">// Monadic bind (chain) for lists
function chain(xs, f) {
return [].concat.apply([], xs.map(f));
}
// [m..n]
function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
return m + i;
});
}
function factors_naive(n) {
return chain( range(1, n), function (x) { // monadic chain/bind
return n % x ? [] : [x]; // monadic fail or inject/return
});
}
factors_naive(6)</syntaxhighlight>
Output:
<syntaxhighlight lang="javascript">[1, 2, 3, 6]</syntaxhighlight>
Translating the Haskell (lows and highs) example
<syntaxhighlight lang="javascript">console.log(
(function (lstTest) {
// INTEGER FACTORS
function integerFactors(n) {
var rRoot = Math.sqrt(n),
intRoot = Math.floor(rRoot),
lows = range(1, intRoot).filter(function (x) {
return (n % x) === 0;
});
// for perfect squares, we can drop the head of the 'highs' list
return lows.concat(lows.map(function (x) {
return n / x;
}).reverse().slice((rRoot === intRoot) | 0));
}
// [m .. n]
function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
return m + i;
});
}
/*************************** TESTING *****************************/
// TABULATION OF RESULTS IN SPACED AND ALIGNED COLUMNS
function alignedTable(lstRows, lngPad, fnAligned) {
var lstColWidths = range(0, lstRows.reduce(function (a, x) {
return x.length > a ? x.length : a;
}, 0) - 1).map(function (iCol) {
return lstRows.reduce(function (a, lst) {
var w = lst[iCol] ? lst[iCol].toString().length : 0;
return (w > a) ? w : a;
}, 0);
});
return lstRows.map(function (lstRow) {
return lstRow.map(function (v, i) {
return fnAligned(v, lstColWidths[i] + lngPad);
}).join('')
}).join('\n');
}
function alignRight(n, lngWidth) {
var s = n.toString();
return Array(lngWidth - s.length + 1).join(' ') + s;
}
// TEST
return '\nintegerFactors(n)\n\n' + alignedTable(
lstTest.map(integerFactors).map(function (x, i) {
return [lstTest[i], '-->'].concat(x);
}), 2, alignRight
) + '\n';
})([25, 45, 53, 64, 100, 102, 120, 12345, 32766, 32767])
);</syntaxhighlight>
Output:
<syntaxhighlight lang="javascript">integerFactors(n)
25 --> 1 5 25
45 --> 1 3 5 9 15 45
53 --> 1 53
64 --> 1 2 4 8 16 32 64
100 --> 1 2 4 5 10 20 25 50 100
102 --> 1 2 3 6 17 34 51 102
120 --> 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
12345 --> 1 3 5 15 823 2469 4115 12345
32766 --> 1 2 3 6 43 86 127 129 254 258 381 762 5461 10922 16383 32766
32767 --> 1 7 31 151 217 1057 4681 32767
</syntaxhighlight>
====ES6====
<syntaxhighlight lang="javascript">(function (lstTest) {
'use strict';
// INTEGER FACTORS
// integerFactors :: Int -> [Int]
let integerFactors = (n) => {
let rRoot = Math.sqrt(n),
intRoot = Math.floor(rRoot),
lows = range(1, intRoot)
.filter(x => (n % x) === 0);
// for perfect squares, we can drop
// the head of the 'highs' list
return lows.concat(lows
.map(x => n / x)
.reverse()
.slice((rRoot === intRoot) | 0)
);
},
// range :: Int -> Int -> [Int]
range = (m, n) => Array.from({
length: (n - m) + 1
}, (_, i) => m + i);
/*************************** TESTING *****************************/
// TABULATION OF RESULTS IN SPACED AND ALIGNED COLUMNS
let alignedTable = (lstRows, lngPad, fnAligned) => {
var lstColWidths = range(
0, lstRows
.reduce(
(a, x) => (x.length > a ? x.length : a),
0
) - 1
)
.map((iCol) => lstRows
.reduce((a, lst) => {
let w = lst[iCol] ? lst[iCol].toString()
.length : 0;
return (w > a) ? w : a;
}, 0));
return lstRows.map((lstRow) =>
lstRow.map((v, i) => fnAligned(
v, lstColWidths[i] + lngPad
))
.join('')
)
.join('\n');
},
alignRight = (n, lngWidth) => {
let s = n.toString();
return Array(lngWidth - s.length + 1)
.join(' ') + s;
};
// TEST
return '\nintegerFactors(n)\n\n' + alignedTable(lstTest
.map(integerFactors)
.map(
(x, i) => [lstTest[i], '-->'].concat(x)
), 2, alignRight
) + '\n';
})([25, 45, 53, 64, 100, 102, 120, 12345, 32766, 32767]);</syntaxhighlight>
{{Out}}
<pre>
integerFactors(n)
25 --> 1 5 25
45 --> 1 3 5 9 15 45
53 --> 1 53
64 --> 1 2 4 8 16 32 64
100 --> 1 2 4 5 10 20 25 50 100
102 --> 1 2 3 6 17 34 51 102
120 --> 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
12345 --> 1 3 5 15 823 2469 4115 12345
32766 --> 1 2 3 6 43 86 127 129 254 258 381 762 5461 10922 16383 32766
32767 --> 1 7 31 151 217 1057 4681 32767
</pre>
=={{header|jq}}==
{{Works with|jq|1.4}}
<
def factors:
. as $num
Line 1,269 ⟶ 4,102:
(45, 53, 64) | "\(.): \(factors)" ;
task</
{{Out}}
$ jq -n -M -r -c -f factors.jq
Line 1,277 ⟶ 4,110:
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Primes
""" Return the factors of n, including 1, n """
function factors(n::T)::Vector{T} where T <: Integer
sort(vec(map(prod, Iterators.product((p.^(0:m) for (p, m) in eachfactor(n))...))))
end
const examples = [28, 45, 53, 64, 6435789435768]
for n in examples
@time println("The factors of $n are: $(factors(n))")
end
</syntaxhighlight>
{{out}}
<pre>
The factors of 28 are: [1, 2, 4, 7, 14, 28]
0.330684 seconds (784.75 k allocations: 39.104 MiB, 3.17% gc time)
The factors of 45 are: [1, 3, 5, 9, 15, 45]
0.000117 seconds (56 allocations: 2.672 KiB)
The factors of 53 are: [1, 53]
0.000102 seconds (35 allocations: 1.516 KiB)
The factors of 64 are: [1, 2, 4, 8, 16, 32, 64]
0.000093 seconds (56 allocations: 3.172 KiB)
The factors of 6435789435768 are: [1, 2, 3, 4, 6, 7, 8, 11, 12, 14, 21, 22, 24, 28,
33, 42, 44, 56, 66, 77, 84, 88, 132, 154, 168, 191, 231, 264, 308, 382, 462, 573,
616, 764, 924, 1146, 1337, 1528, 1848, 2101, 2292, 2674, 4011, 4202, 4584, 5348,
6303, 8022, 8404, 10696, 12606, 14707, 16044, 16808, 25212, 29414, 32088, 44121,
50424, 58828, 88242, 117656, 176484, 352968, 18233351, 36466702, 54700053, 72933404,
109400106, 127633457, 145866808, 200566861, 218800212, 255266914, 382900371,
401133722, 437600424, 510533828, 601700583, 765800742, 802267444, 1021067656,
1203401166, 1403968027, 1531601484, 1604534888, 2406802332, 2807936054, 3063202968,
3482570041, 4211904081, 4813604664, 5615872108, 6965140082, 8423808162, 10447710123,
11231744216, 13930280164, 16847616324, 20895420246, 24377990287, 27860560328,
33695232648, 38308270451, 41790840492, 48755980574, 73133970861, 76616540902,
83581680984, 97511961148, 114924811353, 146267941722, 153233081804, 195023922296,
229849622706, 268157893157, 292535883444, 306466163608, 459699245412, 536315786314,
585071766888, 804473679471, 919398490824, 1072631572628, 1608947358942, 2145263145256,
3217894717884, 6435789435768]
0.000249 seconds (451 allocations: 24.813 KiB)
</pre>
=={{header|K}}==
<
equivalent to:
q)f:{i:{y where x=y*x div y}[x ; 1+ til floor sqrt x]; distinct i,x div reverse i}
f 120
Line 1,319 ⟶ 4,172:
/ Number of factors for 3491888400 .. 3491888409
#:'f' 3491888400+!10
1920 16 4 4 12 16 32 16 8 24</
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">fun printFactors(n: Int) {
if (n < 1) return
print("$n => ")
(1..n / 2)
.filter { n % it == 0 }
.forEach { print("$it ") }
println(n)
}
fun main(args: Array<String>) {
val numbers = intArrayOf(11, 21, 32, 45, 67, 96)
for (number in numbers) printFactors(number)
}</syntaxhighlight>
{{out}}
<pre>
11 => 1 11
21 => 1 3 7 21
32 => 1 2 4 8 16 32
45 => 1 3 5 9 15 45
67 => 1 67
96 => 1 2 3 4 6 8 12 16 24 32 48 96
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def factors
{def factors.r
{lambda {:num :i :N}
{if {> :i :N}
then
else {if {= {% :num :i} 0}
then :i
{if {not {= {/ :num :i} :i}}
then {/ :num :i}
else}
else}
{factors.r :num {+ :i 1} :N} }}}
{lambda {:n}
{S.sort < {factors.r :n 1 {sqrt :n}}}}}
-> factors
{factors 45}
-> 1 3 5 9 15 45
{factors 53}
-> 1 53
{factors 64}
-> 1 2 4 8 16 32 64
</syntaxhighlight>
=={{header|LFE}}==
Line 1,326 ⟶ 4,231:
This following function is elegant looking and concise. However, it will not handle large numbers well: it will consume a great deal of memory (on one large number, the function consumed 4.3GB of memory on my desktop machine):
<
(defun factors (n)
(list-comp
((<- i (when (== 0 (rem n i))) (lists:seq 1 (trunc (/ n 2)))))
i))
</syntaxhighlight>
===Non-Stack-Consuming===
This version will not consume the stack (this function only used 18MB of memory on my machine with a ridiculously large number):
<
(defun factors (n)
"Tail-recursive prime factors function."
Line 1,349 ⟶ 4,254:
((n k acc)
(factors n (+ k 1) acc)))
</syntaxhighlight>
{{out}}
<pre>
> (factors 10677106534462215678539721403561279)
(104729 104729 104729 98731 98731 32579 29269 1)
</
=={{header|
<syntaxhighlight lang="lingo">on factors(n)
res = [1]
repeat with i = 2 to n/2
if n mod i = 0 then res.add(i)
end repeat
res.add(n)
return res
end</syntaxhighlight>
<syntaxhighlight lang="lingo">put factors(45)
-- [1, 3, 5, 9, 15, 45]
put factors(53)
-- [1, 53]
put factors(64)
-- [1, 2, 4, 8, 16, 32, 64]</syntaxhighlight>
=={{header|Logo}}==
<
output filter [equal? 0 modulo :n ?] iseq 1 :n
end
show factors 28 ; [1 2 4 7 14 28]</
=={{header|Lua}}==
<
local f = {}
Line 1,504 ⟶ 4,297:
return f
end</
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
\\ Factors of an integer
\\ For act as BASIC's FOR (if N<1 no loop start)
FORM 60,40
SET SWITCHES "+FOR"
MODULE LikeBasic {
10 INPUT N%
20 FOR I%=1 TO N%
30 IF N%/I%=INT(N%/I%) THEN PRINT I%,
40 NEXT I%
50 PRINT
}
CALL LikeBasic
SET SWITCHES "-FOR"
MODULE LikeM2000 {
DEF DECIMAL N%, I%
INPUT N%
IF N%<1 THEN EXIT
FOR I%=1 TO N% {
IF N% MOD I%=0 THEN PRINT I%,
}
PRINT
}
CALL LikeM2000
</syntaxhighlight>
=={{header|Maple}}==
<syntaxhighlight lang="maple">
numtheory:-divisors(n);
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
=={{header|MATLAB}} / {{header|Octave}}==
<
f = factor(n); % prime decomposition
K = dec2bin(0:2^length(f)-1)-'0'; % generate all possible permutations
Line 1,528 ⟶ 4,348:
disp(F);
end;
</
{{out}}
<pre>
>> fact(12)
Line 1,548 ⟶ 4,368:
=={{header|Maxima}}==
The builtin <code>divisors</code> function does this.
<
(%o96) {1,2,4,5,10,20,25,50,100}</
Such a function could be implemented like so:
<
apply( cartesian_product,
map( lambda([fac],
setify(makelist(fac[1]^i, i, 0, fac[2]))),
ifactors(n))));</
=={{header|MAXScript}}==
<syntaxhighlight lang="maxscript">
fn factors n =
(
return (for i = 1 to n+1 where mod n i == 0 collect i)
)
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="maxscript">
factors 3
#(1, 3)
Line 1,576 ⟶ 4,398:
factors 54
#(1, 2, 3, 6, 9, 18, 27, 54)
</syntaxhighlight>
=={{header|Mercury}}==
Line 1,593 ⟶ 4,415:
===fac.m===
<
:- interface.
Line 1,632 ⟶ 4,454:
factor(N) = Factors :- factor(N, Factors).
:- end_module fac.</
===Use and output===
Line 1,641 ⟶ 4,463:
factor(999, [1,3,9,27,37,111,333,999])
factor(12345678, [1,2,3,6,9,18,47,94,141,282,423,846,14593,29186,43779,87558,131337,262674,685871,1371742,2057613,4115226,6172839,12345678])</nowiki></pre>
=={{header|min}}==
{{works with|min|0.19.6}}
<syntaxhighlight lang="min">(mod 0 ==) :divisor?
(() 0 shorten) :new
(new (over swons 'pred dip) pick times nip) :iota
(
:n
n sqrt int iota ; Only consider numbers up to sqrt(n).
(n swap divisor?) filter =f1
f1 (n swap div) map reverse =f2 ; "Mirror" the list of divisors at sqrt(n).
(f1 last f2 first ==) (f2 rest #f2) when ; Handle perfect squares.
f1 f2 concat
) :factors
24 factors puts!
9 factors puts!
11 factors puts!</syntaxhighlight>
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">factors = function(n)
result = [1]
for i in range(2, n)
if n % i == 0 then result.push i
end for
return result
end function
while true
n = val(input("Number to factor (0 to quit)? "))
if n <= 0 then break
print factors(n)
end while</syntaxhighlight>
{{out}}
<pre>Number to factor (0 to quit)? 42
[1, 2, 3, 6, 7, 14, 21, 42]
Number to factor (0 to quit)? 101
[1, 101]
Number to factor (0 to quit)? 360
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]
Number to factor (0 to quit)? 0</pre>
=={{header|МК-61/52}}==
Line 1,651 ⟶ 4,515:
=={{header|MUMPS}}==
<
If num<1 Quit "Too small a number"
If num["." Quit "Not an integer"
Line 1,661 ⟶ 4,525:
w $$factors(45) ; [1,3,5,9,15,45]
w $$factors(53) ; [1,53]
w $$factors(64) ; [1,2,4,8,16,32,64]</
=={{header|Nanoquery}}==
<syntaxhighlight lang="nanoquery">n = int(input())
for i in range(1, n / 2)
if (n % i = 0)
print i + " "
end
end
println n</syntaxhighlight>
=={{header|NetRexx}}==
{{trans|REXX}}
<
* 21.04.2013 Walter Pachl
* 21.04.2013 add method main to accept argument(s)
Line 1,699 ⟶ 4,573:
If j*j=x Then /*for a square number as input */
lo=lo j /* add its square root */
return lo hi /* return both lists */</
{{out}}
<pre>java divl 1 10
1 -> 1
Line 1,714 ⟶ 4,589:
=={{header|Nim}}==
<
proc factors(n: int): seq[int] =
var fs:
for x in 1 .. int(sqrt(float(n))):
if n mod x == 0:
fs.incl(x)
fs.incl(n div x)
for x in fs:
result.add(x)
echo factors(45)</
=={{header|Niue}}==
<
[ n not-factor [ , ] when ] else ] n times n ] 'factors ;
Line 1,741 ⟶ 4,615:
53 factors .s .clr ( => 1 53 ) newline
64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline
12 factors .s .clr ( => 1 2 3 4 6 12 ) </
=={{header|Oberon-2}}==
Oxford Oberon-2
<
MODULE Factors;
IMPORT Out,SYSTEM;
Line 1,811 ⟶ 4,685:
Out.Int(v.len,6);Out.String(" factors");Out.Ln
END Factors.
</syntaxhighlight>
{{out}}
<pre>
1
Line 1,820 ⟶ 4,694:
4 factors
</pre>
=={{header|Objeck}}==
<
use Structure;
Line 1,858 ⟶ 4,733:
}
}
}</
=={{header|OCaml}}==
<
let factors n =
List.filter (fun v -> (n mod v) = 0) (range n)</
=={{header|Odin}}==
Uses built-in dynamic arrays, and only checks up to the square root
<syntaxhighlight lang="odin">
package main
import "core:fmt"
import "core:slice"
factors :: proc(n: int) -> [dynamic]int {
d := 1
factors := make([dynamic]int)
for {
q := n / d
r := n % d
if d >= q {
if d == q && r == 0 {
append(&factors, d)
}
slice.sort(factors[:])
return factors
}
if r == 0 {
append(&factors, d, q)
}
d += 1
}
}
main :: proc() {
for n in ([?]int{100, 108, 999, 255, 256, 257}) {
a := factors(n)
fmt.println("The factors of", n, "are", a)
delete(a)
}
}
</syntaxhighlight>
{{Out}}
<pre>
The factors of 100 are [1, 2, 4, 5, 10, 20, 25, 50, 100]
The factors of 108 are [1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108]
The factors of 999 are [1, 3, 9, 27, 37, 111, 333, 999]
The factors of 255 are [1, 3, 5, 15, 17, 51, 85, 255]
The factors of 256 are [1, 2, 4, 8, 16, 32, 64, 128, 256]
The factors of 257 are [1, 257]
</pre>
=={{header|Oforth}}==
<
120 factors println</
{{out}}
Line 1,878 ⟶ 4,801:
=={{header|Oz}}==
<
fun {Factors N}
Sqr = {Float.toInt {Sqrt {Int.toFloat N}}}
Line 1,897 ⟶ 4,820:
end
in
{Show {Factors 53}}</
=={{header|Panda}}==
Panda has a factor function already, it's defined as:
<syntaxhighlight lang="panda">fun factor(n) type integer->integer
f where n.mod(1..n=>f)==0
45.factor</syntaxhighlight>
=={{header|PARI/GP}}==
<syntaxhighlight lang
=={{header|Pascal}}==
{{trans|Fortran}}
{{works with|Free Pascal|2.6.2}}
<
var
i, number: integer;
Line 1,923 ⟶ 4,853:
write(i, number/i);
writeln;
end.</
{{out}}
<pre>
Enter a number between 1 and 2147483647: 49
Line 1,933 ⟶ 4,863:
</pre>
===
{{works with|Free Pascal}}
like [[http://rosettacode.org/wiki/Factors_of_an_integer#Prime_factoring C Prime_factoring]].<BR>
Insertion sort was much faster, because mostly not so many factors need to be sorted.<BR>
"runtime overhead" +25% instead +100% for quicksort against no sort.<BR>
Especially fast for consecutive integers.
<syntaxhighlight lang="pascal">program FacOfInt;
// gets factors of consecutive integers fast
// limited to 1.2e11
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils
{$IFDEF WINDOWS},Windows{$ENDIF}
;
//######################################################################
//prime decomposition
const
//HCN(86) > 1.2E11 = 128,501,493,120 count of divs = 4096 7 3 1 1 1 1 1 1 1
HCN_DivCnt = 4096;
type
tItem = Uint64;
tDivisors = array [0..HCN_DivCnt] of tItem;
tpDivisor = pUint64;
const
//used odd size for test only
SizePrDeFe = 32768;//*72 <= 64kb level I or 2 Mb ~ level 2 cache
type
tdigits = array [0..31] of Uint32;
//the first number with 11 different prime factors =
//2*3*5*7*11*13*17*19*23*29*31 = 2E11
//56 byte
tprimeFac = packed record
pfSumOfDivs,
pfRemain : Uint64;
pfDivCnt : Uint32;
pfMaxIdx : Uint32;
pfpotPrimIdx : array[0..9] of word;
pfpotMax : array[0..11] of byte;
end;
tpPrimeFac = ^tprimeFac;
tPrimeDecompField = array[0..SizePrDeFe-1] of tprimeFac;
tPrimes = array[0..65535] of Uint32;
var
{$ALIGN 8}
SmallPrimes: tPrimes;
{$ALIGN 32}
PrimeDecompField :tPrimeDecompField;
pdfIDX,pdfOfs: NativeInt;
procedure InitSmallPrimes;
//get primes. #0..65535.Sieving only odd numbers
const
MAXLIMIT = (821641-1) shr 1;
var
pr : array[0..MAXLIMIT] of byte;
p,j,d,flipflop :NativeUInt;
Begin
SmallPrimes[0] := 2;
fillchar(pr[0],SizeOf(pr),#0);
p := 0;
repeat
repeat
p +=1
until pr[p]= 0;
j := (p+1)*p*2;
if j>MAXLIMIT then
BREAK;
d := 2*p+1;
repeat
pr[j] := 1;
j += d;
until j>MAXLIMIT;
until false;
SmallPrimes[1] := 3;
SmallPrimes[2] := 5;
j := 3;
d := 7;
flipflop := (2+1)-1;//7+2*2,11+2*1,13,17,19,23
p := 3;
repeat
if pr[p] = 0 then
begin
SmallPrimes[j] := d;
inc(j);
end;
d += 2*flipflop;
p+=flipflop;
flipflop := 3-flipflop;
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
end;
function OutPots(pD:tpPrimeFac;n:NativeInt):Ansistring;
var
s: String[31];
chk,p,i: NativeInt;
Begin
str(n,s);
result := s+' :';
with pd^ do
begin
str(pfDivCnt:3,s);
result += s+' : ';
chk := 1;
For n := 0 to pfMaxIdx-1 do
Begin
if n>0 then
result += '*';
p := SmallPrimes[pfpotPrimIdx[n]];
chk *= p;
str(p,s);
result += s;
i := pfpotMax[n];
if i >1 then
Begin
str(pfpotMax[n],s);
result += '^'+s;
repeat
chk *= p;
dec(i);
until i <= 1;
end;
end;
p := pfRemain;
If p >1 then
Begin
str(p,s);
chk *= p;
result += '*'+s;
end;
str(chk,s);
result += '_chk_'+s+'<';
str(pfSumOfDivs,s);
result += '_SoD_'+s+'<';
end;
end;
function smplPrimeDecomp(n:Uint64):tprimeFac;
var
pr,i,pot,fac,q :NativeUInt;
Begin
with result do
Begin
pfDivCnt := 1;
pfSumOfDivs := 1;
pfRemain := n;
pfMaxIdx := 0;
pfpotPrimIdx[0] := 1;
pfpotMax[0] := 0;
i := 0;
while i < High(SmallPrimes) do
begin
pr := SmallPrimes[i];
q := n DIV pr;
//if n < pr*pr
if pr > q then
BREAK;
if n = pr*q then
Begin
pfpotPrimIdx[pfMaxIdx] := i;
pot := 0;
fac := pr;
repeat
n := q;
q := n div pr;
pot+=1;
fac *= pr;
until n <> pr*q;
pfpotMax[pfMaxIdx] := pot;
pfDivCnt *= pot+1;
pfSumOfDivs *= (fac-1)DIV(pr-1);
inc(pfMaxIdx);
end;
inc(i);
end;
pfRemain := n;
if n > 1 then
Begin
pfDivCnt *= 2;
pfSumOfDivs *= n+1
end;
end;
end;
function CnvtoBASE(var dgt:tDigits;n:Uint64;base:NativeUint):NativeInt;
//n must be multiple of base aka n mod base must be 0
var
q,r: Uint64;
i : NativeInt;
Begin
fillchar(dgt,SizeOf(dgt),#0);
i := 0;
n := n div base;
result := 0;
repeat
r := n;
q := n div base;
r -= q*base;
n := q;
dgt[i] := r;
inc(i);
until (q = 0);
//searching lowest pot in base
result := 0;
while (result<i) AND (dgt[result] = 0) do
inc(result);
inc(result);
end;
function IncByBaseInBase(var dgt:tDigits;base:NativeInt):NativeInt;
var
q :NativeInt;
Begin
result := 0;
q := dgt[result]+1;
if q = base then
repeat
dgt[result] := 0;
inc(result);
q := dgt[result]+1;
until q <> base;
dgt[result] := q;
result +=1;
end;
function SieveOneSieve(var pdf:tPrimeDecompField):boolean;
var
dgt:tDigits;
i,
begin
n := pdfOfs;
if n+SizePrDeFe >= sqr(SmallPrimes[High(SmallPrimes)]) then
//init
for i := 0 to SizePrDeFe-1 do
begin
with pdf[i] do
Begin
pfDivCnt := 1;
pfSumOfDivs := 1;
pfRemain := n+i;
pfMaxIdx := 0;
pfpotPrimIdx[0] := 0;
pfpotMax[0] := 0;
end;
end;
//first factor 2. Make n+i even
i := (pdfIdx+n) AND 1;
IF (n = 0) AND (pdfIdx<2) then
i := 2;
repeat
begin
pfpotMax[0] := j;
pfRemain := (n+i) shr j;
pfSumOfDivs := (Uint64(1) shl (j+1))-1;
pfDivCnt := j+1;
end;
i += 2;
until i >=SizePrDeFe;
//i now index in SmallPrimes
i := 0;
maxP := trunc(sqrt(n+SizePrDeFe))+1;
repeat
//search next prime that is in bounds of sieve
if n = 0 then
begin
repeat
inc(i);
pr := SmallPrimes[i];
k := pr-n MOD pr;
if k < SizePrDeFe then
break;
until pr > MaxP;
end
else
begin
repeat
inc(i);
pr := SmallPrimes[i];
k := pr-n MOD pr;
if (k = pr) AND (n>0) then
k:= 0;
if k < SizePrDeFe then
break;
until pr > MaxP;
end;
//no need to use higher primes
if pr*pr > n+SizePrDeFe then
//j is power of prime
repeat
with pdf[k] do
Begin
pfpotPrimIdx[pfMaxIdx] := i;
pfpotMax[pfMaxIdx] := j;
pfDivCnt *= j+1;
fac := pr;
repeat
pfRemain := pfRemain DIV pr;
dec(j);
fac *= pr;
until j<= 0;
pfSumOfDivs *= (fac-1)DIV(pr-1);
inc(pfMaxIdx);
k += pr;
j := IncByBaseInBase(dgt,pr);
end;
until k >= SizePrDeFe;
until false;
//correct sum of & count of divisors
for i := 0 to High(pdf) do
Begin
with pdf[i] do
begin
j := pfRemain;
if j <> 1 then
begin
pfSumOFDivs *= (j+1);
pfDivCnt *=2;
end;
end;
end;
result := true;
end;
function NextSieve:boolean;
begin
dec(pdfIDX,SizePrDeFe);
inc(pdfOfs,SizePrDeFe);
result := SieveOneSieve(PrimeDecompField);
end;
function GetNextPrimeDecomp:tpPrimeFac;
begin
if pdfIDX >= SizePrDeFe then
if Not(NextSieve) then
EXIT(NIL);
result := @PrimeDecompField[pdfIDX];
inc(pdfIDX);
end;
function Init_Sieve(n:NativeUint):boolean;
//Init Sieve pdfIdx,pdfOfs are Global
begin
pdfIdx := n MOD SizePrDeFe;
pdfOfs := n-pdfIdx;
result := SieveOneSieve(PrimeDecompField);
end;
procedure InsertSort(pDiv:tpDivisor; Left, Right : NativeInt );
var
I, J: NativeInt;
Pivot : tItem;
begin
for i:= 1 + Left to Right do
begin
Pivot:= pDiv[i];
j:= i - 1;
while (j >= Left) and (pDiv[j] > Pivot) do
begin
pDiv[j+1]:=pDiv[j];
Dec(j);
end;
pDiv[j+1]:= pivot;
end;
end;
procedure GetDivisors(pD:tpPrimeFac;var Divs:tDivisors);
var
pDivs : tpDivisor;
pPot : UInt64;
i,len,j,l,p,k: Int32;
Begin
pDivs := @Divs[0];
pDivs[0] := 1;
len := 1;
l := 1;
with pD^ do
Begin
For i := 0 to pfMaxIdx-1 do
begin
//Multiply every divisor before with the new primefactors
//and append them to the list
k := pfpotMax[i];
p := SmallPrimes[pfpotPrimIdx[i]];
pPot :=1;
repeat
pPot *= p;
For j := 0 to len-1 do
Begin
pDivs[l]:= pPot*pDivs[j];
inc(l);
end;
dec(k);
until k<=0;
len := l;
end;
p := pfRemain;
If p >1 then
begin
For j := 0 to len-1 do
Begin
pDivs[l]:= p*pDivs[j];
inc(l);
end;
len := l;
end;
end;
//Sort. Insertsort much faster than QuickSort in this special case
InsertSort(pDivs,0,len-1);
//end marker
pDivs[len] :=0;
end;
procedure AllFacsOut(var Divs:tdivisors;proper:boolean=true);
var
k,j: Int32;
Begin
k := 0;
j := 1;
if Proper then
j:= 2;
repeat
IF Divs[j] = 0 then
BREAK;
write(Divs[k],',');
inc(j);
inc(k);
until false;
writeln(Divs[k]);
end;
var
pPrimeDecomp :tpPrimeFac;
Mypd : tPrimeFac;
Divs:tDivisors;
T0:Int64;
n : NativeUInt;
Begin
InitSmallPrimes;
T0 := GetTickCount64;
n := 0;
Init_Sieve(0);
repeat
pPrimeDecomp:= GetNextPrimeDecomp;
GetDivisors(pPrimeDecomp,Divs);
inc(n);
until n > 10*1000*1000+1;
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
GetDivisors(pPrimeDecomp,Divs);
AllFacsOut(Divs,true);
AllFacsOut(Divs,false);
writeln('simple version');
T0 := GetTickCount64;
n := 0;
repeat
Mypd:= smplPrimeDecomp(n);
GetDivisors(@Mypd,Divs);
inc(n);
until n > 10*1000*1000+1;
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
GetDivisors(@Mypd,Divs);
AllFacsOut(Divs,true);
AllFacsOut(Divs,false);
end.</syntaxhighlight>
{{out}}
<pre>
TIO.RUN
//out-commented GetDivisors, but still calculates sum of divisors and count of divisors
runtime 0.555 s
1,11,909091
1,11,909091,10000001
simple version
runtime 8.167 s
1,11,909091
1,11,909091,10000001
Real time: 8.868 s CPU share: 99.57 %
//with GetDivisors
runtime 1.815 s
1,11,909091
1,11,909091,10000001
simple version
runtime 11.057 s
1,11,909091
1,11,909091,10000001
Real time: 13.082 s CPU share: 99.16 %
</pre>
=={{header|Perl}}==
<
{
my($n) = @_;
return grep { $n % $_ == 0 }(1 .. $n);
}
print join ' ',factors(64), "\n";</
Or more intelligently:
<
my $n = shift;
$n = -$n if $n < 0;
Line 1,997 ⟶ 5,391:
@divisors, map { $_*$_ == $n ? () : int($n/$_) } reverse @divisors;
}
print join " ", factors(64), "\n";</
One could also use a module, e.g.:
{{libheader|ntheory}}
<
print join " ", divisors(12345678), "\n";
# Alternately something like: fordivisors { say } 12345678; </
=={{header|Phix}}==
There is a builtin factors(n), which takes an optional second parameter to include 1 and n:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12345</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{1,3,5,15,823,2469,4115,12345}
</pre>
You can find the implementation of factors(), prime_factors(), and prime_powers() in builtins\pfactors.e,<br>
and mpz_factors(), mpz_prime_factors(), and mpz_pollard_rho() in mpfr.e for larger numbers, for example:
<div style="font-size: 11px">
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- [p2js/integer() bugs]</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3491888400</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"factors"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- {2,3,4,5,"...",698377680,872972100,1163962800.0,1745944200.0," (1,918 factors)"}</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3491888400</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"factors"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- {2,3,4,5,"...",698377680,872972100,1163962800.0,1745944200.0," (1,918 factors)"}
-- If the include1 parameter is 1 or "BOTH", then you'll also get 1 and 3491888400</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3491888400</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- {2,3,5,7,11,13,17,19}</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">prime_powers</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3491888400</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- <nowiki>{{</nowiki>2,4},{3,3},{5,2},{7,1},{11,1},{13,1},{17,1},{19,1<nowiki>}}</nowiki></span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">vslice</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3491888400"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- {2,3,5,7,11,13,17,19}</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3491888400"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- <nowiki>{{</nowiki>2,4},{3,3},{5,2},{7,1},{11,1},{13,1},{17,1},{19,1<nowiki>}}</nowiki>
-- Note that mpz_prime_factors() only accepts string or mpz, and not a raw native atom/integer.</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;">108233175859200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- 666</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">108233175859200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- 666</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"10677106534462215678539721403561279"</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- <nowiki>{{</nowiki>29269,1},{32579,1},{98731,2},{104729,3<nowiki>}}</nowiki></span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"factors"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- {1,29269,"...","364792324112959639158827476291","10677106534462215678539721403561279"," (48 factors)"}</span>
<!--</syntaxhighlight>-->
</div>
Note the value in (string) d exceeds the precision limit of an IEEE-754 float, and would trigger a suitable human readable run-time error if passed to any of the non-mpz routines. Sadly, 1200034005600070000008900000000000000000 exceeds the capabilities of my mpz_pollard_rho(), which I had hoped to showcase - perhaps you would like to improve it?
=={{header|Phixmonti}}==
<syntaxhighlight lang="phixmonti">/# Rosetta Code problem: http://rosettacode.org/wiki/Factors_of_an_integer
by Galileo, 05/2022 #/
include ..\Utilitys.pmt
def Factors >ps
( ( 1 tps 2 / ) for tps over mod if drop endif endfor ps> )
enddef
11 Factors
21 Factors
32 factors
45 factors
67 factors
96 factors
pstack</syntaxhighlight>
{{out}}
<pre>
[[1, 11], [1, 3, 7, 21], [1, 2, 4, 8, 16, 32], [1, 3, 5, 9, 15, 45], [1, 67], [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96]]
=== Press any key to exit ===</pre>
=={{header|PHP}}==
<
$factors = array(1, $n);
for($i = 2; $i * $i <= $n; $i++){
Line 2,020 ⟶ 5,467:
sort($factors);
return $factors;
}</
=={{header|Picat}}==
===List comprehension===
<syntaxhighlight lang="picat">factors(N) = [[D,N // D] : D in 1..N.sqrt.floor, N mod D == 0].flatten.sort_remove_dups.</syntaxhighlight>
===Recursion===
{{trans|Prolog}}
<syntaxhighlight lang="picat">factors2(N,Fs) :-
integer(N),
N > 0,
Fs = findall(F,factors2_(N,F)).sort_remove_dups.
factors2_(N,F) :-
L = floor(sqrt(N)),
between(1,L,X),
0 == N mod X,
( F = X ; F = N // X ).</syntaxhighlight>
===Loop using set===
<syntaxhighlight lang="picat">factors3(N) = Set.keys.sort =>
Set = new_set(),
Set.put(1),
Set.put(N),
foreach(I in 1..floor(sqrt(N)), N mod I == 0)
Set.put(I),
Set.put(N//I)
end.</syntaxhighlight>
===Comparison===
Let's compare with 18! (6402373705728000) which has 14688 factors. The recursive version is slightly faster than the loop + set version.
<syntaxhighlight lang="picat">go =>
N = 6402373705728000, % factorial(18),
println("factors:"),
time(_Fs1 = factors(N)) ,
println("factors2:"),
time(factors2(N,_Fs2)),
println("factors3:"),
time(Fs3=factors3(N)).len),
</syntaxhighlight>
{{out}}
<pre>factors:
CPU time 3.938 seconds.
factors2:
CPU time 3.108 seconds.
factors3:
CPU time 3.159 seconds.</pre>
=={{header|PicoLisp}}==
<
(filter
'((D) (=0 (% N D)))
(range 1 N) ) )</
=={{header|PILOT}}==
<syntaxhighlight lang="pilot">T :Enter a number.
A :#n
C :factor = 1
T :The factors of #n are:
*Loop
C :remainder = n % factor
T ( remainder = 0 ) :#factor
J ( factor = n ) :*Finished
C :factor = factor + 1
J :*Loop
*Finished
END:</syntaxhighlight>
=={{header|PL/0}}==
{{trans|GW-BASIC}}
PL/0 does not handle strings. So, no prompt. The program waits for entering a number, and then displays the factors.
<syntaxhighlight lang="pascal">
var n, absn, ndiv2, i;
begin
? n;
absn := n;
if n < 0 then absn := -n;
ndiv2 := absn / 2;
i := 1;
while i <= ndiv2 do
begin
if (absn / i) * i = absn then ! i;
i := i + 1
end;
! absn;
end.
</syntaxhighlight>
4 runs.
{{in}}
<pre>1</pre>
{{out}}
<pre>
1
</pre>
{{in}}
<pre>11</pre>
{{out}}
<pre>
1
2
3
4
6
12
</pre>
{{in}}
<pre>13</pre>
{{out}}
<pre>
1
13
</pre>
{{in}}
<pre>-22222</pre>
{{out}}
<pre>
1
2
41
82
271
542
11111
22222
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pli">factors: procedure options(main);
declare i binary( 15 )fixed;
declare n binary( 15 )fixed;
do n = 90 to 100;
put skip list( 'factors of: ', n, ': ' );
do i = 1 to n;
if mod(n, i) = 0 then put edit( i )(f(4));
end;
end;
end factors;
</syntaxhighlight>
{{out}}
<pre>
factors of: 90 : 1 2 3 5 6 9 10 15 18 30 45 90
factors of: 91 : 1 7 13 91
factors of: 92 : 1 2 4 23 46 92
factors of: 93 : 1 3 31 93
factors of: 94 : 1 2 47 94
factors of: 95 : 1 5 19 95
factors of: 96 : 1 2 3 4 6 8 12 16 24 32 48 96
factors of: 97 : 1 97
factors of: 98 : 1 2 7 14 49 98
factors of: 99 : 1 3 9 11 33 99
factors of: 100 : 1 2 4 5 10 20 25 50 100
</pre>
See also [[#Polyglot:PL/I and PL/M]]
=={{header|PL/M}}==
See [[#Polyglot:PL/I and PL/M]]
=={{header|Plain English}}==
<syntaxhighlight lang="plainenglish">To run:
Start up.
Show the factors of 11.
Show the factors of 21.
Show the factors of 519.
Wait for the escape key.
Shut down.
To show the factors of a number:
Write "The factors of " then the number then ":" on the console.
Find a square root of the number.
Loop.
If a counter is past the square root, write "" on the console; exit.
Divide the number by the counter giving a quotient and a remainder.
If the remainder is 0, show the counter and the quotient.
Repeat.
A factor is a number.
To show a factor and another factor:
If the factor is not the other factor, write "" then the factor then " " then the other factor then " " on the console without advancing; exit.
Write "" then the factor on the console without advancing.</syntaxhighlight>
{{out}}
<pre>
The factors of 11:
1 11
The factors of 21:
1 21 3 7
The factors of 519:
1 519 3 173
</pre>
=={{header|Polyglot:PL/I and PL/M}}==
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
Should work with many PL/I implementations.
<br>
The PL/I include file "pg.inc" can be found on the [[Polyglot:PL/I and PL/M]] page.
Note the use of text in column 81 onwards to hide the PL/I specifics from the PL/M compiler.
<syntaxhighlight lang="pli">factors_100H: procedure options (main);
/* PL/I DEFINITIONS */
%include 'pg.inc';
/* PL/M DEFINITIONS: CP/M BDOS SYSTEM CALL AND CONSOLE I/O ROUTINES, ETC. */ /*
DECLARE BINARY LITERALLY 'ADDRESS', CHARACTER LITERALLY 'BYTE';
DECLARE SADDR LITERALLY '.', BIT LITERALLY 'BYTE';
DECLARE FIXED LITERALLY ' ';
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PRSTRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PRCHAR: PROCEDURE( C ); DECLARE C CHARACTER; CALL BDOS( 2, C ); END;
PRNL: PROCEDURE; CALL PRCHAR( 0DH ); CALL PRCHAR( 0AH ); END;
PRNUMBER: PROCEDURE( N );
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR( 6 ) BYTE, W BYTE;
N$STR( W := LAST( N$STR ) ) = '$';
N$STR( W := W - 1 ) = '0' + ( ( V := N ) MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL BDOS( 9, .N$STR( W ) );
END PRNUMBER;
MODF: PROCEDURE( A, B )ADDRESS;
DECLARE ( A, B )ADDRESS;
RETURN( A MOD B );
END MODF;
/* END LANGUAGE DEFINITIONS */
/* TASK */
DECLARE ( I, N ) FIXED BINARY;
DO N = 90 TO 100;
CALL PRSTRING( SADDR( 'FACTORS OF: $' ) );
CALL PRNUMBER( N );
CALL PRCHAR( ':' );
DO I = 1 TO N;
IF MODF( N, I ) = 0 THEN DO;
CALL PRCHAR( ' ' );
CALL PRNUMBER( I );
END;
END;
CALL PRNL;
END;
EOF: end factors_100H;</syntaxhighlight>
{{out}}
<pre>
FACTORS OF: 90: 1 2 3 5 6 9 10 15 18 30 45 90
FACTORS OF: 91: 1 7 13 91
FACTORS OF: 92: 1 2 4 23 46 92
FACTORS OF: 93: 1 3 31 93
FACTORS OF: 94: 1 2 47 94
FACTORS OF: 95: 1 5 19 95
FACTORS OF: 96: 1 2 3 4 6 8 12 16 24 32 48 96
FACTORS OF: 97: 1 97
FACTORS OF: 98: 1 2 7 14 49 98
FACTORS OF: 99: 1 3 9 11 33 99
FACTORS OF: 100: 1 2 4 5 10 20 25 50 100
</pre>
=={{header|PowerShell}}==
===Straightforward but slow===
<
1..$a | Where-Object { $a % $_ -eq 0 }
}</
This one uses a range of integers up to the target number and just filters it using the <code>Where-Object</code> cmdlet. It's very slow though, so it is not very usable for larger numbers.
===A little more clever===
<
1..[Math]::Sqrt($a) `
| Where-Object { $a % $_ -eq 0 } `
| ForEach-Object { $_; $a / $_ } `
| Sort-Object -Unique
}</
Here the range of integers is only taken up to the square root of the number, the same filtering applies. Afterwards the corresponding larger factors are calculated and sent down the pipeline along with the small ones found earlier.
=={{header|ProDOS}}==
Uses the math module:
<
do /delimspaces %% -a- >b
printline Factors of -a-: -b- </
=={{header|Prolog}}==
'''Simple Brute Force Implementation'''
<syntaxhighlight lang="prolog">
brute_force_factors( N , Fs ) :-
integer(N) ,
Line 2,063 ⟶ 5,761:
setof( F , ( between(1,N,F) , N mod F =:= 0 ) , Fs )
.
</syntaxhighlight>
'''A Slightly Smarter Implementation'''
<syntaxhighlight lang="prolog">
smart_factors(N,Fs) :-
integer(N) ,
Line 2,079 ⟶ 5,777:
( F = X ; F is N // X )
.
</syntaxhighlight>
Not every Prolog has <code>between/3</code>: you might need this:
<syntaxhighlight lang="prolog">
between(X,Y,Z) :-
Line 2,100 ⟶ 5,798:
between1(X1,Y,Z)
.
</syntaxhighlight>
{{out}}
<pre>
?- N=36 ,( brute_force_factors(N,Factors) ; smart_factors(N,Factors) ).
Line 2,132 ⟶ 5,830:
N = 32767, Factors = [1, 7, 31, 151, 217, 1057, 4681, 32767] .
</pre>
=={{header|Python}}==
Naive and slow but simplest (check all numbers from 1 to n):
<
return [i for i in range(1, n + 1) if not n%i]</
Slightly better (realize that there are no factors between n/2 and n):
<
return [i for i in range(1, n//2 + 1) if not n%i] + [n]
>>> factors(45)
[1, 3, 5, 9, 15, 45]</
Much better (realize that factors come in pairs, the smaller of which is no bigger than sqrt(n)):
<syntaxhighlight lang
factors1,
if n % x == 0:
x += 1
if x * x == n:
factors1.append(x)
factors1.extend(reversed(factors2))
return factors1
for i in 45, 53, 64:
print("%i: factors: %s" % (i, factor(i)))</syntaxhighlight><pre>
45: factors: [1, 3, 5, 9, 15, 45]
53: factors: [1, 53]
64: factors: [1, 2, 4, 8, 16, 32, 64]</
More efficient when factoring many numbers:
<
def factors(n):
Line 2,205 ⟶ 5,881:
for e in prime_powers(n):
r += [a*b for a in r for b in e]
return r</
=={{header|Quackery}}==
<code>sqrt+</code> is defined at [[Isqrt (integer square root) of X#Quackery]]. It returns the integer square root and remainder (i.e. the square root of 11 is 3 remainder 2, because three squared plus two equals eleven.) If the number is a perfect square the remainder is zero. This is used to remove a duplicate factor from the list of factors which is generated when finding the factors of a perfect square.
The nest editing at the end of the definition (i.e. the code after the <code>drop</code> on a line by itself) removes a duplicate factor if there is one, and arranges the factors in ascending numerical order at the same time.
<syntaxhighlight lang="text"> [ [] swap
dup sqrt+ 0 = dip
[ times
[ dup i^ 1+ /mod iff
drop done
rot join
i^ 1+ join swap ]
drop
dup size 2 / split ]
if [ -1 split drop ]
swap join ] is factors ( n --> [ )
20 times
[ i^ 1+ dup
dup 10 < if sp
echo
say ": "
factors witheach
[ echo i if say ", " ]
cr ]</syntaxhighlight>
{{out}}
<pre> 1: 1
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
7: 1, 7
8: 1, 2, 4, 8
9: 1, 3, 9
10: 1, 2, 5, 10
11: 1, 11
12: 1, 2, 3, 4, 6, 12
13: 1, 13
14: 1, 2, 7, 14
15: 1, 3, 5, 15
16: 1, 2, 4, 8, 16
17: 1, 17
18: 1, 2, 3, 6, 9, 18
19: 1, 19
20: 1, 2, 4, 5, 10, 20
</pre>
=={{header|R}}==
===Array solution===
<syntaxhighlight lang="rsplus">factors <- function(n)
{
if(length(n) > 1)
Line 2,218 ⟶ 5,946:
one.to.n[(n %% one.to.n) == 0]
}
}</syntaxhighlight>
{{out}}
<pre>
>factors(60)
[1] 1 2 3 4 5 6 10 12 15 20 30 60
>factors(c(45, 53, 64))
[[1]]
[1] 1 3 5 9 15 45
Line 2,230 ⟶ 5,959:
[1] 1 2 4 8 16 32 64
</pre>
===Filter solution===
With identical output, a more idiomatic way is to use R's Filter.
<syntaxhighlight lang="rsplus">factors <- function(n) c(Filter(function(x) n %% x == 0, seq_len(n %/% 2)), n)
#Vectorize is an interesting alternative to the previous solution's lapply.
manyFactors <- function(vec) Vectorize(factors)(vec)</syntaxhighlight>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 2,263 ⟶ 5,997:
(time (length (divisors huge)))
;; And this one clocks at 17ms
</syntaxhighlight>
=={{header|
(formerly Perl 6)
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku" line>sub factors (Int $n) { (1..$n).grep($n %% *) }</syntaxhighlight>
=={{header|Red}}==
<syntaxhighlight lang="red">Red []
factors: function [n [integer!]] [
n: absolute n
collect [
repeat i (sq: sqrt n) - 1 [
if n % i = 0 [
keep i
keep n / i
]
]
if sq = sq: to-integer sq [keep sq]
]
]
foreach num [
24
-64 ; negative
64 ; square
101 ; prime
123456789 ; large
][
print mold/flat sort factors num
]</syntaxhighlight>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout <Factors 120>>;
}
Factors {
s.N = <Factors (s.N 1)>;
(s.N s.D), <Compare s.N <* s.D s.D>>: '-' = ;
(s.N s.D), <Divmod s.N s.D>: {
(s.D) 0 = s.D;
(s.F) 0 = s.D <Factors (s.N <+ 1 s.D>)> s.F;
(s.X) s.Y = <Factors (s.N <+ 1 s.D>)>;
};
};</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120</pre>
=={{header|Relation}}==
<syntaxhighlight lang="relation">
program factors(num)
relation fact
insert 1
set i = 2
while i < num / 2
if num / i = floor(num/i)
insert i
end if
set i = i + 1
end while
insert num
print
end program
</syntaxhighlight>
=={{header|REXX}}==
===optimized version===
This REXX version has no effective limits on the number of decimal digits in the number to be factored [by adjusting the number of digits (precision)].
This REXX version also supports negative integers and zero.
It also indicates '''primes''' in the output listing as well as the <u>number</u> of divisors.
It also displays a final count of the number of primes found.
This REXX version is about '''22%''' faster than the alternate REXX version (2<sup>nd</sup> version).
<syntaxhighlight lang="rexx">/*REXX program displays divisors of any [negative/zero/positive] integer or a range.*/
parse arg LO HI inc . /*obtain the optional args*/
HI= word(HI LO 20, 1); LO= word(LO 1,1); inc= word(inc 1,1) /*define the range options*/
w= length(HI) + 2; numeric digits max(9, w-2); != '∞' /*decimal digits for // */
@.=left('',7); @.1= "{unity}"; @.2= '[prime]'; @.!= " {∞} " /*define some literals. */
say center('n', w) "#divisors" center('divisors', 60) /*display the header. */
say copies('═', w) "═════════" copies('═' , 60) /* " " separator. */
pn= 0 /*count of prime numbers. */
do k=2 until sq.k>=HI; sq.k= k*k /*memoization for squares.*/
end /*k*/
do n=LO to HI by inc; $= divs(n); #= words($) /*get list of divs; # divs*/
if $==! then do; #= !; $= ' (infinite)'; end /*handle case for infinity*/
p= @.#; if n<0 then if n\==-1 then p= @.. /* " " " negative*/
if p==@.2 then pn= pn + 1 /*Prime? Then bump counter*/
say center(n, w) center('['#"]", 9) "──► " p ' ' $
end /*n*/ /* [↑] process a range of integers. */
say
say right(pn, 20) ' primes were found.' /*display the number of primes found. */
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
divs: procedure expose sq.; parse arg x 1 b; a=1 /*set X and B to the 1st argument. */
if x<2 then do; x= abs(x); if x==1 then return 1; if x==0 then return '∞'; b=x
end
odd= x // 2 /* [↓] process EVEN or ODD ints. ___*/
do j=2+odd by 1+odd while sq.j<x /*divide by all the integers up to √ x */
if x//j==0 then do; a=a j; b=x%j b; end /*÷? Add divisors to α and ß lists*/
end /*j*/ /* [↑] % ≡ integer division. ___*/
if sq.j==x then return a j b /*Was X a square? Then insert √ x */
return a b /*return the divisors of both lists. */</syntaxhighlight>
{{out|output|text= when using the input of: <tt> -6 200 </tt>}}
(Shown at <big>'''<sup>3</sup>/<sub>4</sub>'''</big> size.)
<pre style="font-size:75%;height:85ex">
n #divisors divisors
══════ ═════════ ════════════════════════════════════════════════════════════
-6 [4] ──► 1 2 3 6
-5 [2] ──► 1 5
-4 [3] ──► 1 2 4
-3 [2] ──► 1 3
-2 [2] ──► 1 2
-1 [1] ──► {unity} 1
0 [∞] ──► {∞} (infinite)
1 [1] ──► {unity} 1
2 [2] ──► [prime] 1 2
3 [2] ──► [prime] 1 3
4 [3] ──► 1 2 4
5 [2] ──► [prime] 1 5
6 [4] ──► 1 2 3 6
7 [2] ──► [prime] 1 7
8 [4] ──► 1 2 4 8
9 [3] ──► 1 3 9
10 [4] ──► 1 2 5 10
11 [2] ──► [prime] 1 11
12 [6] ──► 1 2 3 4 6 12
13 [2] ──► [prime] 1 13
14 [4] ──► 1 2 7 14
15 [4] ──► 1 3 5 15
16 [5] ──► 1 2 4 8 16
17 [2] ──► [prime] 1 17
18 [6] ──► 1 2 3 6 9 18
19 [2] ──► [prime] 1 19
20 [6] ──► 1 2 4 5 10 20
21 [4] ──► 1 3 7 21
22 [4] ──► 1 2 11 22
23 [2] ──► [prime] 1 23
24 [8] ──► 1 2 3 4 6 8 12 24
25 [3] ──► 1 5 25
26 [4] ──► 1 2 13 26
27 [4] ──► 1 3 9 27
28 [6] ──► 1 2 4 7 14 28
29 [2] ──► [prime] 1 29
30 [8] ──► 1 2 3 5 6 10 15 30
31 [2] ──► [prime] 1 31
32 [6] ──► 1 2 4 8 16 32
33 [4] ──► 1 3 11 33
34 [4] ──► 1 2 17 34
35 [4] ──► 1 5 7 35
36 [9] ──► 1 2 3 4 6 9 12 18 36
37 [2] ──► [prime] 1 37
38 [4] ──► 1 2 19 38
39 [4] ──► 1 3 13 39
40 [8] ──► 1 2 4 5 8 10 20 40
41 [2] ──► [prime] 1 41
42 [8] ──► 1 2 3 6 7 14 21 42
43 [2] ──► [prime] 1 43
44 [6] ──► 1 2 4 11 22 44
45 [6] ──► 1 3 5 9 15 45
46 [4] ──► 1 2 23 46
47 [2] ──► [prime] 1 47
48 [10] ──► 1 2 3 4 6 8 12 16 24 48
49 [3] ──► 1 7 49
50 [6] ──► 1 2 5 10 25 50
51 [4] ──► 1 3 17 51
52 [6] ──► 1 2 4 13 26 52
53 [2] ──► [prime] 1 53
54 [8] ──► 1 2 3 6 9 18 27 54
55 [4] ──► 1 5 11 55
56 [8] ──► 1 2 4 7 8 14 28 56
57 [4] ──► 1 3 19 57
58 [4] ──► 1 2 29 58
59 [2] ──► [prime] 1 59
60 [12] ──► 1 2 3 4 5 6 10 12 15 20 30 60
61 [2] ──► [prime] 1 61
62 [4] ──► 1 2 31 62
63 [6] ──► 1 3 7 9 21 63
64 [7] ──► 1 2 4 8 16 32 64
65 [4] ──► 1 5 13 65
66 [8] ──► 1 2 3 6 11 22 33 66
67 [2] ──► [prime] 1 67
68 [6] ──► 1 2 4 17 34 68
69 [4] ──► 1 3 23 69
70 [8] ──► 1 2 5 7 10 14 35 70
71 [2] ──► [prime] 1 71
72 [12] ──► 1 2 3 4 6 8 9 12 18 24 36 72
73 [2] ──► [prime] 1 73
74 [4] ──► 1 2 37 74
75 [6] ──► 1 3 5 15 25 75
76 [6] ──► 1 2 4 19 38 76
77 [4] ──► 1 7 11 77
78 [8] ──► 1 2 3 6 13 26 39 78
79 [2] ──► [prime] 1 79
80 [10] ──► 1 2 4 5 8 10 16 20 40 80
81 [5] ──► 1 3 9 27 81
82 [4] ──► 1 2 41 82
83 [2] ──► [prime] 1 83
84 [12] ──► 1 2 3 4 6 7 12 14 21 28 42 84
85 [4] ──► 1 5 17 85
86 [4] ──► 1 2 43 86
87 [4] ──► 1 3 29 87
88 [8] ──► 1 2 4 8 11 22 44 88
89 [2] ──► [prime] 1 89
90 [12] ──► 1 2 3 5 6 9 10 15 18 30 45 90
91 [4] ──► 1 7 13 91
92 [6] ──► 1 2 4 23 46 92
93 [4] ──► 1 3 31 93
94 [4] ──► 1 2 47 94
95 [4] ──► 1 5 19 95
96 [12] ──► 1 2 3 4 6 8 12 16 24 32 48 96
97 [2] ──► [prime] 1 97
98 [6] ──► 1 2 7 14 49 98
99 [6] ──► 1 3 9 11 33 99
100 [9] ──► 1 2 4 5 10 20 25 50 100
101 [2] ──► [prime] 1 101
102 [8] ──► 1 2 3 6 17 34 51 102
103 [2] ──► [prime] 1 103
104 [8] ──► 1 2 4 8 13 26 52 104
105 [8] ──► 1 3 5 7 15 21 35 105
106 [4] ──► 1 2 53 106
107 [2] ──► [prime] 1 107
108 [12] ──► 1 2 3 4 6 9 12 18 27 36 54 108
109 [2] ──► [prime] 1 109
110 [8] ──► 1 2 5 10 11 22 55 110
111 [4] ──► 1 3 37 111
112 [10] ──► 1 2 4 7 8 14 16 28 56 112
113 [2] ──► [prime] 1 113
114 [8] ──► 1 2 3 6 19 38 57 114
115 [4] ──► 1 5 23 115
116 [6] ──► 1 2 4 29 58 116
117 [6] ──► 1 3 9 13 39 117
118 [4] ──► 1 2 59 118
119 [4] ──► 1 7 17 119
120 [16] ──► 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
121 [3] ──► 1 11 121
122 [4] ──► 1 2 61 122
123 [4] ──► 1 3 41 123
124 [6] ──► 1 2 4 31 62 124
125 [4] ──► 1 5 25 125
126 [12] ──► 1 2 3 6 7 9 14 18 21 42 63 126
127 [2] ──► [prime] 1 127
128 [8] ──► 1 2 4 8 16 32 64 128
129 [4] ──► 1 3 43 129
130 [8] ──► 1 2 5 10 13 26 65 130
131 [2] ──► [prime] 1 131
132 [12] ──► 1 2 3 4 6 11 12 22 33 44 66 132
133 [4] ──► 1 7 19 133
134 [4] ──► 1 2 67 134
135 [8] ──► 1 3 5 9 15 27 45 135
136 [8] ──► 1 2 4 8 17 34 68 136
137 [2] ──► [prime] 1 137
138 [8] ──► 1 2 3 6 23 46 69 138
139 [2] ──► [prime] 1 139
140 [12] ──► 1 2 4 5 7 10 14 20 28 35 70 140
141 [4] ──► 1 3 47 141
142 [4] ──► 1 2 71 142
143 [4] ──► 1 11 13 143
144 [15] ──► 1 2 3 4 6 8 9 12 16 18 24 36 48 72 144
145 [4] ──► 1 5 29 145
146 [4] ──► 1 2 73 146
147 [6] ──► 1 3 7 21 49 147
148 [6] ──► 1 2 4 37 74 148
149 [2] ──► [prime] 1 149
150 [12] ──► 1 2 3 5 6 10 15 25 30 50 75 150
151 [2] ──► [prime] 1 151
152 [8] ──► 1 2 4 8 19 38 76 152
153 [6] ──► 1 3 9 17 51 153
154 [8] ──► 1 2 7 11 14 22 77 154
155 [4] ──► 1 5 31 155
156 [12] ──► 1 2 3 4 6 12 13 26 39 52 78 156
157 [2] ──► [prime] 1 157
158 [4] ──► 1 2 79 158
159 [4] ──► 1 3 53 159
160 [12] ──► 1 2 4 5 8 10 16 20 32 40 80 160
161 [4] ──► 1 7 23 161
162 [10] ──► 1 2 3 6 9 18 27 54 81 162
163 [2] ──► [prime] 1 163
164 [6] ──► 1 2 4 41 82 164
165 [8] ──► 1 3 5 11 15 33 55 165
166 [4] ──► 1 2 83 166
167 [2] ──► [prime] 1 167
168 [16] ──► 1 2 3 4 6 7 8 12 14 21 24 28 42 56 84 168
169 [3] ──► 1 13 169
170 [8] ──► 1 2 5 10 17 34 85 170
171 [6] ──► 1 3 9 19 57 171
172 [6] ──► 1 2 4 43 86 172
173 [2] ──► [prime] 1 173
174 [8] ──► 1 2 3 6 29 58 87 174
175 [6] ──► 1 5 7 25 35 175
176 [10] ──► 1 2 4 8 11 16 22 44 88 176
177 [4] ──► 1 3 59 177
178 [4] ──► 1 2 89 178
179 [2] ──► [prime] 1 179
180 [18] ──► 1 2 3 4 5 6 9 10 12 15 18 20 30 36 45 60 90 180
181 [2] ──► [prime] 1 181
182 [8] ──► 1 2 7 13 14 26 91 182
183 [4] ──► 1 3 61 183
184 [8] ──► 1 2 4 8 23 46 92 184
185 [4] ──► 1 5 37 185
186 [8] ──► 1 2 3 6 31 62 93 186
187 [4] ──► 1 11 17 187
188 [6] ──► 1 2 4 47 94 188
189 [8] ──► 1 3 7 9 21 27 63 189
190 [8] ──► 1 2 5 10 19 38 95 190
191 [2] ──► [prime] 1 191
192 [14] ──► 1 2 3 4 6 8 12 16 24 32 48 64 96 192
193 [2] ──► [prime] 1 193
194 [4] ──► 1 2 97 194
195 [8] ──► 1 3 5 13 15 39 65 195
196 [9] ──► 1 2 4 7 14 28 49 98 196
197 [2] ──► [prime] 1 197
198 [12] ──► 1 2 3 6 9 11 18 22 33 66 99 198
199 [2] ──► [prime] 1 199
200 [12] ──► 1 2 4 5 8 10 20 25 40 50 100 200
</pre>
===Alternate Version===
{{trans|REXX optimized version}}
<syntaxhighlight lang="rexx">/* REXX ***************************************************************
* Program to calculate and show divisors of positive integer(s).
* 03.08.2012 Walter Pachl simplified the above somewhat
Line 2,553 ⟶ 6,354:
If j*j=x Then /*for a square number as input */
lo=lo j /* add its square root */
return lo hi /* return both lists */</
{{out|output|text= when using the default input:}}
(Shown at <big>'''<sup>3</sup>/<sub>4</sub>'''</big> size.)
<pre style="font-size:75%;height:85ex">
n = 1 divisors = 1
n = 2 divisors = 1 2
n = 3 divisors = 1 3
n = 4 divisors = 1 2 4
n = 5 divisors = 1 5
n = 6 divisors = 1 2 3 6
n = 7 divisors = 1 7
n = 8 divisors = 1 2 4 8
n = 9 divisors = 1 3 9
n = 10 divisors = 1 2 5 10
n = 11 divisors = 1 11
n = 12 divisors = 1 2 3 4 6 12
n = 13 divisors = 1 13
n = 14 divisors = 1 2 7 14
n = 15 divisors = 1 3 5 15
n = 16 divisors = 1 2 4 8 16
n = 17 divisors = 1 17
n = 18 divisors = 1 2 3 6 9 18
n = 19 divisors = 1 19
n = 20 divisors = 1 2 4 5 10 20
n = 21 divisors = 1 3 7 21
n = 22 divisors = 1 2 11 22
n = 23 divisors = 1 23
n = 24 divisors = 1 2 3 4 6 8 12 24
n = 25 divisors = 1 5 25
n = 26 divisors = 1 2 13 26
n = 27 divisors = 1 3 9 27
n = 28 divisors = 1 2 4 7 14 28
n = 29 divisors = 1 29
n = 30 divisors = 1 2 3 5 6 10 15 30
n = 31 divisors = 1 31
n = 32 divisors = 1 2 4 8 16 32
n = 33 divisors = 1 3 11 33
n = 34 divisors = 1 2 17 34
n = 35 divisors = 1 5 7 35
n = 36 divisors = 1 2 3 4 6 9 12 18 36
n = 37 divisors = 1 37
n = 38 divisors = 1 2 19 38
n = 39 divisors = 1 3 13 39
n = 40 divisors = 1 2 4 5 8 10 20 40
n = 41 divisors = 1 41
n = 42 divisors = 1 2 3 6 7 14 21 42
n = 43 divisors = 1 43
n = 44 divisors = 1 2 4 11 22 44
n = 45 divisors = 1 3 5 9 15 45
n = 46 divisors = 1 2 23 46
n = 47 divisors = 1 47
n = 48 divisors = 1 2 3 4 6 8 12 16 24 48
n = 49 divisors = 1 7 49
n = 50 divisors = 1 2 5 10 25 50
n = 51 divisors = 1 3 17 51
n = 52 divisors = 1 2 4 13 26 52
n = 53 divisors = 1 53
n = 54 divisors = 1 2 3 6 9 18 27 54
n = 55 divisors = 1 5 11 55
n = 56 divisors = 1 2 4 7 8 14 28 56
n = 57 divisors = 1 3 19 57
n = 58 divisors = 1 2 29 58
n = 59 divisors = 1 59
n = 60 divisors = 1 2 3 4 5 6 10 12 15 20 30 60
n = 61 divisors = 1 61
n = 62 divisors = 1 2 31 62
n = 63 divisors = 1 3 7 9 21 63
n = 64 divisors = 1 2 4 8 16 32 64
n = 65 divisors = 1 5 13 65
n = 66 divisors = 1 2 3 6 11 22 33 66
n = 67 divisors = 1 67
n = 68 divisors = 1 2 4 17 34 68
n = 69 divisors = 1 3 23 69
n = 70 divisors = 1 2 5 7 10 14 35 70
n = 71 divisors = 1 71
n = 72 divisors = 1 2 3 4 6 8 9 12 18 24 36 72
n = 73 divisors = 1 73
n = 74 divisors = 1 2 37 74
n = 75 divisors = 1 3 5 15 25 75
n = 76 divisors = 1 2 4 19 38 76
n = 77 divisors = 1 7 11 77
n = 78 divisors = 1 2 3 6 13 26 39 78
n = 79 divisors = 1 79
n = 80 divisors = 1 2 4 5 8 10 16 20 40 80
n = 81 divisors = 1 3 9 27 81
n = 82 divisors = 1 2 41 82
n = 83 divisors = 1 83
n = 84 divisors = 1 2 3 4 6 7 12 14 21 28 42 84
n = 85 divisors = 1 5 17 85
n = 86 divisors = 1 2 43 86
n = 87 divisors = 1 3 29 87
n = 88 divisors = 1 2 4 8 11 22 44 88
n = 89 divisors = 1 89
n = 90 divisors = 1 2 3 5 6 9 10 15 18 30 45 90
n = 91 divisors = 1 7 13 91
n = 92 divisors = 1 2 4 23 46 92
n = 93 divisors = 1 3 31 93
n = 94 divisors = 1 2 47 94
n = 95 divisors = 1 5 19 95
n = 96 divisors = 1 2 3 4 6 8 12 16 24 32 48 96
n = 97 divisors = 1 97
n = 98 divisors = 1 2 7 14 49 98
n = 99 divisors = 1 3 9 11 33 99
n = 100 divisors = 1 2 4 5 10 20 25 50 100
n = 101 divisors = 1 101
n = 102 divisors = 1 2 3 6 17 34 51 102
n = 103 divisors = 1 103
n = 104 divisors = 1 2 4 8 13 26 52 104
n = 105 divisors = 1 3 5 7 15 21 35 105
n = 106 divisors = 1 2 53 106
n = 107 divisors = 1 107
n = 108 divisors = 1 2 3 4 6 9 12 18 27 36 54 108
n = 109 divisors = 1 109
n = 110 divisors = 1 2 5 10 11 22 55 110
n = 111 divisors = 1 3 37 111
n = 112 divisors = 1 2 4 7 8 14 16 28 56 112
n = 113 divisors = 1 113
n = 114 divisors = 1 2 3 6 19 38 57 114
n = 115 divisors = 1 5 23 115
n = 116 divisors = 1 2 4 29 58 116
n = 117 divisors = 1 3 9 13 39 117
n = 118 divisors = 1 2 59 118
n = 119 divisors = 1 7 17 119
n = 120 divisors = 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
n = 121 divisors = 1 11 121
n = 122 divisors = 1 2 61 122
n = 123 divisors = 1 3 41 123
n = 124 divisors = 1 2 4 31 62 124
n = 125 divisors = 1 5 25 125
n = 126 divisors = 1 2 3 6 7 9 14 18 21 42 63 126
n = 127 divisors = 1 127
n = 128 divisors = 1 2 4 8 16 32 64 128
n = 129 divisors = 1 3 43 129
n = 130 divisors = 1 2 5 10 13 26 65 130
n = 131 divisors = 1 131
n = 132 divisors = 1 2 3 4 6 11 12 22 33 44 66 132
n = 133 divisors = 1 7 19 133
n = 134 divisors = 1 2 67 134
n = 135 divisors = 1 3 5 9 15 27 45 135
n = 136 divisors = 1 2 4 8 17 34 68 136
n = 137 divisors = 1 137
n = 138 divisors = 1 2 3 6 23 46 69 138
n = 139 divisors = 1 139
n = 140 divisors = 1 2 4 5 7 10 14 20 28 35 70 140
n = 141 divisors = 1 3 47 141
n = 142 divisors = 1 2 71 142
n = 143 divisors = 1 11 13 143
n = 144 divisors = 1 2 3 4 6 8 9 12 16 18 24 36 48 72 144
n = 145 divisors = 1 5 29 145
n = 146 divisors = 1 2 73 146
n = 147 divisors = 1 3 7 21 49 147
n = 148 divisors = 1 2 4 37 74 148
n = 149 divisors = 1 149
n = 150 divisors = 1 2 3 5 6 10 15 25 30 50 75 150
n = 151 divisors = 1 151
n = 152 divisors = 1 2 4 8 19 38 76 152
n = 153 divisors = 1 3 9 17 51 153
n = 154 divisors = 1 2 7 11 14 22 77 154
n = 155 divisors = 1 5 31 155
n = 156 divisors = 1 2 3 4 6 12 13 26 39 52 78 156
n = 157 divisors = 1 157
n = 158 divisors = 1 2 79 158
n = 159 divisors = 1 3 53 159
n = 160 divisors = 1 2 4 5 8 10 16 20 32 40 80 160
n = 161 divisors = 1 7 23 161
n = 162 divisors = 1 2 3 6 9 18 27 54 81 162
n = 163 divisors = 1 163
n = 164 divisors = 1 2 4 41 82 164
n = 165 divisors = 1 3 5 11 15 33 55 165
n = 166 divisors = 1 2 83 166
n = 167 divisors = 1 167
n = 168 divisors = 1 2 3 4 6 7 8 12 14 21 24 28 42 56 84 168
n = 169 divisors = 1 13 169
n = 170 divisors = 1 2 5 10 17 34 85 170
n = 171 divisors = 1 3 9 19 57 171
n = 172 divisors = 1 2 4 43 86 172
n = 173 divisors = 1 173
n = 174 divisors = 1 2 3 6 29 58 87 174
n = 175 divisors = 1 5 7 25 35 175
n = 176 divisors = 1 2 4 8 11 16 22 44 88 176
n = 177 divisors = 1 3 59 177
n = 178 divisors = 1 2 89 178
n = 179 divisors = 1 179
n = 180 divisors = 1 2 3 4 5 6 9 10 12 15 18 20 30 36 45 60 90 180
n = 181 divisors = 1 181
n = 182 divisors = 1 2 7 13 14 26 91 182
n = 183 divisors = 1 3 61 183
n = 184 divisors = 1 2 4 8 23 46 92 184
n = 185 divisors = 1 5 37 185
n = 186 divisors = 1 2 3 6 31 62 93 186
n = 187 divisors = 1 11 17 187
n = 188 divisors = 1 2 4 47 94 188
n = 189 divisors = 1 3 7 9 21 27 63 189
n = 190 divisors = 1 2 5 10 19 38 95 190
n = 191 divisors = 1 191
n = 192 divisors = 1 2 3 4 6 8 12 16 24 32 48 64 96 192
n = 193 divisors = 1 193
n = 194 divisors = 1 2 97 194
n = 195 divisors = 1 3 5 13 15 39 65 195
n = 196 divisors = 1 2 4 7 14 28 49 98 196
n = 197 divisors = 1 197
n = 198 divisors = 1 2 3 6 9 11 18 22 33 66 99 198
n = 199 divisors = 1 199
n = 200 divisors = 1 2 4 5 8 10 20 25 40 50 100 200
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
nArray = list(100)
n = 45
j = 0
for i = 1 to n
if n % i = 0 j = j + 1 nArray[j] = i ok
next
see "Factors of " + n + " = "
for i = 1 to j
see "" + nArray[i] + " "
next
</syntaxhighlight>
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.7}}
≪ → n
≪ { } DUP 1 n √ '''FOR''' d
'''IF''' n d MOD NOT
'''THEN'''
d + n d /
'''IF''' DUP d ≠ '''THEN''' ROT + SWAP '''ELSE''' DROP '''END'''
'''END'''
'''NEXT'''
SWAP +
≫ ≫
'FACTS' STO
45 FACTS
53 FACTS
64 FACTS
{{out}}
<pre>
3: { 1 3 5 9 15 45 }
2: { 1 53 }
1: { 1 2 4 8 16 32 64 }
</pre>
=={{header|Ruby}}==
<
def factors() (1..self).select { |n| (self % n).zero? } end
end
p 45.factors</
[1, 3, 5, 9, 15, 45]
As we only have to loop up to <math>\sqrt{n}</math>, we can write
<
def factors
1.upto(
f << self/i unless i == self/i
f << i
Line 2,571 ⟶ 6,616:
end
end
[45, 53, 64].each {|n| puts "#{n} : #{n.factors}"}</
{{out}}
<pre>
Line 2,578 ⟶ 6,623:
64 : [1, 2, 4, 8, 16, 32, 64]</pre>
===Using the prime library===
<syntaxhighlight lang="ruby">
require 'prime'
def factors m
return [1] if 1==m
primes, powers = Prime.prime_division(m).transpose
ranges = powers.map{|n| (0..n).to_a}
ranges[0].product( *ranges[1..-1] ).
map{|es| primes.zip(es).map{|p,e| p**e}.reduce :*}.
sort
end
[1, 7, 45, 100].each{|n| p factors n}
</syntaxhighlight>
Output:
<pre>
[1]
[1, 7]
[1, 3, 5, 9, 15, 45]
[1, 2, 4, 5, 10, 20, 25, 50, 100]
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn main() {
assert_eq!(vec![1, 2, 4, 5, 10, 10, 20, 25, 50, 100], factor(100)); // asserts that two expressions are equal to each other
assert_eq!(vec![1, 101], factor(101));
}
fn factor(num: i32) -> Vec<i32> {
let mut factors: Vec<i32> = Vec::new(); // creates a new vector for the factors of the number
for i in 1..((num as f32).sqrt() as i32 + 1) {
if num % i == 0 {
factors.push(i); // pushes smallest factor to factors
factors.push(num/i); // pushes largest factor to factors
}
}
factors.sort(); // sorts the factors into numerical order for viewing purposes
factors // returns the factors
}</syntaxhighlight>
Alternative functional version:
<syntaxhighlight lang="rust">
fn factor(n: i32) -> Vec<i32> {
(1..=n).filter(|i| n % i == 0).collect()
}
</syntaxhighlight>
=={{header|Sather}}==
<syntaxhighlight lang="sather">class MAIN is
factors!(n :INT):
loop i ::= 2.upto!( n.flt.sqrt.int );
if n%i = 0 then
yield n / i;
end;
end;
end;
end;
Line 2,638 ⟶ 6,694:
loop l ::= a.elt!;
#OUT + "factors of " + l + ": ";
#OUT + ri + " ";
end;
Line 2,645 ⟶ 6,700:
end;
end;
end;
</syntaxhighlight>
=={{header|Scala}}==
Brute force approach:
<syntaxhighlight
(1 to num).filter { divisor =>
num % divisor == 0
}
}</syntaxhighlight>
Brute force until sqrt(num) is enough, the code above can be edited as follows (Scala 3 enabled)
<syntaxhighlight lang="scala">def factors(num: Int) = {
val list = (1 to math.sqrt(num).floor.toInt).filter(num % _ == 0)
list ++ list.reverse.dropWhile(d => d*d == num).map(num / _)
}</syntaxhighlight>
=={{header|Scheme}}==
This implementation uses a naive trial division algorithm.
<
(define (*factors d)
(cond ((> d n) (list))
Line 2,665 ⟶ 6,726:
(display (factors 1111111))
(newline)</
{{out}}
<pre>
(1 239 4649 1111111)
</pre>
=={{header|Seed7}}==
<
const proc: writeFactors (in integer: number) is func
Line 2,699 ⟶ 6,763:
writeFactors(number);
end for;
end func;</
{{out}}
<pre>
Factors of 45: 1, 45, 3, 15, 5, 9
Factors of 53: 1, 53
Factors of 64: 1, 64, 2, 32, 4, 16, 8
</pre>
=={{header|SequenceL}}==
'''Brute Force Method'''
A simple brute force method using an indexed partial function as a filter.
<syntaxhighlight lang="sequencel">Factors(num(0))[i] := i when num mod i = 0 foreach i within 1 ... num;</syntaxhighlight>
'''Slightly More Efficient Method'''
A slightly more efficient method, only going up to the sqrt(n).
<syntaxhighlight lang="sequencel">Factors(num(0)) :=
let
factorPairs[i] :=
[i] when i = sqrt(num)
else
[i, num/i] when num mod i = 0
foreach i within 1 ... floor(sqrt(num));
in
join(factorPairs);</syntaxhighlight>
=={{header|Sidef}}==
Built-in:
<syntaxhighlight lang="ruby">say divisors(97) #=> [1, 97]
say divisors(2695) #=> [1, 5, 7, 11, 35, 49, 55, 77, 245, 385, 539, 2695]</syntaxhighlight>
Trial-division (slow for large n):
<syntaxhighlight lang="ruby">func divisors(n) {
gather {
{ |d|
take(d, n//d) if d.divides(n)
} << 1..n.isqrt
}.sort.uniq
}
[53, 64, 32766].each {|n|
say "divisors(#{n}): #{divisors(n)}"
}</syntaxhighlight>
{{out}}
<pre>
divisors(53): [1, 53]
divisors(64): [1, 2, 4, 8, 16, 32, 64]
divisors(32766): [1, 2, 3, 6, 43, 86, 127, 129, 254, 258, 381, 762, 5461, 10922, 16383, 32766]
</pre>
=={{header|Slate}}==
<
[
[| :result |
result nextPut: 1.
n primesDo: [| :prime | result nextPut: prime]] writingAs: {}
].</
where <tt>primesDo:</tt> is a part of the standard numerics library:
<
"Decomposes the Integer into primes, applying the block to each (in increasing
order)."
Line 2,730 ⟶ 6,838:
[div: next.
next: next + 2] "Just looks at the next odd integer."
].</
=={{header|Smalltalk}}==
Copied from the Python example, but code added to the Integer built in class:
<syntaxhighlight lang="smalltalk">Integer>>factors
| a |
a := OrderedCollection new.
Line 2,742 ⟶ 6,848:
((self \\ i) = 0) ifTrue: [ a add: i ] ].
a add: self.
^a</
Then use as follows:
<
59 factors -> an OrderedCollection(1 59)
120 factors -> an OrderedCollection(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
</syntaxhighlight>
=={{header|Standard ML}}==
Need to print the list because Standard ML truncates the display of
longer returned lists.
<syntaxhighlight lang="standard ml">fun printIntList ls =
(
List.app (fn n => print(Int.toString n ^ " ")) ls;
print "\n"
);
fun factors n =
let
fun factors'(n, k) =
if k > n then
[]
else if n mod k = 0 then
k :: factors'(n, k+1)
else
factors'(n, k+1)
in
factors'(n,1)
end;
</syntaxhighlight>
Call:
<syntaxhighlight lang="standard ml">printIntList(factors 12345)
printIntList(factors 120)</syntaxhighlight>
{{out}}
<pre>1 3 5 15 823 2469 4115 12345
1 2 3 4 5 6 8 10 12 15 20 24 30 40 60
</pre>
=={{header|Swift}}==
Simple implementation:
<
return filter(1...n) { n % $0 == 0 }
}</
More efficient implementation:
<
func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }
Line 2,774 ⟶ 6,911:
return sorted(result)
}</
Call:
<
println(factors(1))
println(factors(25))
println(factors(63))
println(factors(19))
println(factors(768))</
{{out}}
<pre>[1, 2, 4]
Line 2,789 ⟶ 6,926:
[1, 19]
[1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 768]
</pre>
=={{header|Tailspin}}==
<syntaxhighlight lang="tailspin">
[1..351 -> \(when <?(351 mod $ <=0>)> do $! \)] -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
[1, 3, 9, 13, 27, 39, 117, 351]
</pre>
=={{header|Tcl}}==
<
set factors {}
for {set i 1} {$i <= sqrt($n)} {incr i} {
Line 2,803 ⟶ 6,949:
puts [factors 64]
puts [factors 45]
puts [factors 53]</
{{out}}
<pre>1 2 4 8 16 32 64
1 3 5 9 15 45
Line 2,812 ⟶ 6,959:
This should work in all Bourne-compatible shells, assuming the system has both <tt>sort</tt> and at least one of <tt>bc</tt> or <tt>dc</tt>.
<syntaxhighlight lang="text">factor() {
r=`echo "sqrt($1)" | bc` # or `echo $1 v p | dc`
i=1
Line 2,823 ⟶ 6,970:
done | sort -nu
}
</syntaxhighlight>
=={{header|Ursa}}==
This program takes an integer from the command line and outputs its factors.
<syntaxhighlight lang="ursa">decl int n
set n (int args<1>)
decl int i
for (set i 1) (< i (+ (/ n 2) 1)) (inc i)
if (= (mod n i) 0)
out i " " console
end if
end for
out n endl console</syntaxhighlight>
=={{header|Ursala}}==
The simple way:
<
#import nat
factors "n" = (filter not remainder/"n") nrange(1,"n")</
The complicated way:
<
Another idea would be to approximate an upper bound for the square root of <code>"n"</code> with some bit twiddling such as <code>&!*K31 "n"</code>, which evaluates to a binary number of all 1's half the width of "n" rounded up, and another would be to use the <code>division</code> function to get the quotient and remainder at the same time. Combining these ideas, losing the dummy variable, and cleaning up some other cruft, we have
<
where <code>nleq-<&</code> isn't strictly necessary unless an ordered list is required.
<
example = factors 100</
{{out}}
<pre><1,2,4,5,10,20,25,50,100></pre>
=={{header|Verilog}}==
<syntaxhighlight lang="verilog">
module main;
integer i, n;
initial begin
n = 45;
$write(n, " =>");
for(i = 1; i <= n / 2; i = i + 1) if(n % i == 0) $write(i);
$display(n);
$finish ;
end
endmodule
</syntaxhighlight>
{{out}}
<pre>
45 => 1 3 5 9 15 45
</pre>
=={{header|Wortel}}==
<
factors1 &n !-\%%n @to n
factors_tacit @(\\%% !- @to)
Line 2,851 ⟶ 7,032:
!factors1 720
]]
}</
Returns: <pre>[
[1 2 5 10]
Line 2,857 ⟶ 7,038:
[1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 36 40 45 48 60 72 80 90 120 144 180 240 360 720]
]</pre>
=={{header|V (Vlang)}}==
{{trans|Ring}}
<syntaxhighlight lang="Zig">
fn main() {
mut arr := []int{len: 100}
mut n, mut j := 45, 0
for i in 1..n + 1 {
if n % i == 0 {
j++
arr[j] = i
}
}
print("Factors of ${n} = ")
for i in 1..j + 1 {print(" ${arr[i]} ")}
}
</syntaxhighlight>
{{out}}
<pre>
Factors of 45 = 1 3 5 9 15 45
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int
var a = [11, 21, 32, 45, 67, 96, 159, 723, 1024, 5673, 12345, 32767, 123459, 999997]
System.print("The factors of the following numbers are:")
for (e in a) Fmt.print("$6d => $n", e, Int.divisors(e))</syntaxhighlight>
{{out}}
<pre>
The factors of the following numbers are:
11 => [1, 11]
21 => [1, 3, 7, 21]
32 => [1, 2, 4, 8, 16, 32]
45 => [1, 3, 5, 9, 15, 45]
67 => [1, 67]
96 => [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96]
159 => [1, 3, 53, 159]
723 => [1, 3, 241, 723]
1024 => [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
5673 => [1, 3, 31, 61, 93, 183, 1891, 5673]
12345 => [1, 3, 5, 15, 823, 2469, 4115, 12345]
32767 => [1, 7, 31, 151, 217, 1057, 4681, 32767]
123459 => [1, 3, 7, 21, 5879, 17637, 41153, 123459]
999997 => [1, 757, 1321, 999997]
</pre>
=={{header|X86 Assembly}}==
{{works with|nasm}}
<syntaxhighlight lang="asm">
section .bss
factorArr resd 250 ;big buffer against seg fault
section .text
global _main
_main:
mov ebp, esp; for correct debugging
mov eax, 0x7ffffffe ;number of which we want to know the factors, max num this program works with
mov ebx, eax ;save eax
mov ecx, 1 ;n, factor we test for
mov [factorArr], dword 0
looping:
mov eax, ebx ;restore eax
xor edx, edx ;clear edx
div ecx
cmp edx, 0 ;test if our number % n == 0
jne next
mov edx, [factorArr] ;if yes, we increment the size of the array and append n
inc edx
mov [factorArr+edx*4], ecx ;appending n
mov [factorArr], edx ;storing the new size
next:
mov eax, ecx
cmp eax, ebx ;is n bigger then our number ?
jg end ;if yes we end
inc ecx
jmp looping
end:
mov ecx, factorArr ;pass arr address by ecx
xor eax, eax ;clear eax
mov esp, ebp ;garbage collecting
ret
</syntaxhighlight>
=={{header|XPL0}}==
<
int N0, N, F;
[N0:= 1;
Line 2,875 ⟶ 7,143:
N0:= N0+1;
until KeyHit;
]</
{{out}}
<pre>
1 = 1
Line 2,914 ⟶ 7,182:
=={{header|zkl}}==
{{trans|Chapel}}
<
'wrap(m){((n % m)==0) and T(m,n/m) or Void.Skip}) }
fcn g(n){ [[(m); [1..n.toFloat().sqrt()],'{n%m==0}; '{T(m,n/m)} ]] } // list comprehension</
{{out}}
<pre>
| |||