Basic Data Operation
This is a basic data operation. It represents a fundamental action on a basic data type.
You may see other such operations in theBasic Data Operations category, or:
Integer Operations
Arithmetic |Comparison
Boolean Operations
Bitwise |Logical
String Operations
Concatenation |Interpolation |Comparison |Matching
Memory Operations
Pointers & references |Addresses
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.
(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.
<:1:~>|~#:end:>~x}:str:/={^:wei:~%x<:a:x=$~=}:wei:x<:1:+{>~>x=-#:fin:^:str:}:fin:{{~%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)))
45: factors: [1, 3, 5, 9, 15, 45]53: factors: [1, 53]64: factors: [1, 2, 4, 8, 16, 32, 64]
Very compact version.
* Factors of an integer - 07/10/2015FACTOR CSECT USING FACTOR,R15 set base register LA R7,PG pgi=@pg LA R6,1 i L R3,N loop countLOOP 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+6NEXT 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 callerN DC F'12345' <== input valuePG DC CL132' ' buffer YREGS END FACTOR
1 3 5 15 823 2469 4115 12345
;max input range equals 0 to 0xFFFFFFFF.jsrGetInput;unimplemented routine to get user input for a positive (nonzero) integer.;output of this routine will be in D0.MOVE.LD0,D1;D1 will be used for temp storage.MOVE.L#1,D2;start with 1.computeFactors:DIVUD2,D1;remainder is in top 2 bytes, quotient in bottom 2.MOVE.LD1,D3;temporarily store into D3 to check the remainderSWAPD3;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?BNED2_Wasnt_A_Divisor;if not, D2 was not a factor of D1.JSRPrintD2;unimplemented routine to print D2 to the screen as a decimal number.D2_Wasnt_A_Divisor:MOVE.LD0,D1;restore D1.ADDQ.L#1,D2;increment D2CMP.LD2,D1;is D2 now greater than D1?BLScomputeFactors;if not, loop again;end of program
/* 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 *//*******************************************/.dataszMessDeb: .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 factors100: // standard end of the program mov x0, #0 // return code mov x8, #EXIT // request to exit program svc 0 // perform the system callqNumber: .quad 32767qAdrszCarriageReturn: .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 loop1: // 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 affichageMess2: add x6,x6,#1 // add 1 to loop counter cmp x6,x5 // <= number ? ble 1b // yes loop100: ldp x2,x3,[sp],16 // restaur 2 registers ldp x1,lr,[sp],16 // restaur 2 registers retqAdrszMessDeb: .quad szMessDebqAdrszMessFactor: .quad szMessFactorqAdrsZoneConversion: .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 string2: // 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 loop5: // x4 contains position insertion add x8,x4,1 // init index character output string // at position insertion + one mov x3,#0 // index load characters insertion string6: 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 loop7: // 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 loop8: mov x0,x5 // return output string address b 100f99: // error mov x0,#-1100: 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"
(defunfactors-r(ni)(declare(xargs:measure(nfix(-ni))))(cond((zp(-ni))(listn))((=(modni)0)(consi(factors-rn(1+i))))(t(factors-rn(1+i)))))(defunfactors(n)(factors-rn1))
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 ODRETURNPROC Test(CARD a) PrintF("Factors of %U: ",a) PrintFactors(a) PutE()RETURNPROC Main() Test(1) Test(101) Test(666) Test(1977) Test(2021) Test(6502) Test(12345)RETURNScreenshot from Atari 8-bit computer
Factors of 1: 1Factors of 101: 1, 101Factors of 666: 1, 2, 3, 6, 9, 18, 37,74, 111, 222, 333, 666Factors of 1977: 1, 3, 659, 1977Factors of 2021: 1, 43, 47, 2021Factors of 6502: 1, 2, 3251, 6502Factors of 12345: 1, 3, 5, 15, 823, 2469, 4115, 12345
functionfactor(n:uint):Vector.<uint>{varfactors:Vector.<uint>=newVector.<uint>();for(vari:uint=1;i<=n;i++)if(n%i==0)factors.push(i);returnfactors;}
withAda.Text_IO;withAda.Command_Line;procedureFactorsisNumber:Positive;Test_Nr:Positive:=1;beginifAda.Command_Line.Argument_Count/=1thenAda.Text_IO.Put(Ada.Text_IO.Standard_Error,"Missing argument!");Ada.Command_Line.Set_Exit_Status(Ada.Command_Line.Failure);return;endif;Number:=Positive'Value(Ada.Command_Line.Argument(1));Ada.Text_IO.Put("Factors of"&Positive'Image(Number)&": ");loopifNumbermodTest_Nr=0thenAda.Text_IO.Put(Positive'Image(Test_Nr)&",");endif;exitwhenTest_Nr**2>=Number;Test_Nr:=Test_Nr+1;endloop;Ada.Text_IO.Put_Line(Positive'Image(Number)&".");endFactors;
import mathfunction factor (n:int) { var result = [] function append (v) { if (!(v in result)) { result.append (v) } } var sqrt = cast<int>(Math.sqrt (n)) append (1) for (var i = n-1 ; i >= sqrt ; i--) { if ((n % i) == 0) { append (i) append (n/i) } } append (n) return result.sort()}function printvec (vec) { var comma = "" print ("[") foreach v vec { print (comma + v) comma = ", " } println ("]")}printvec (factor (45))printvec (factor (25))printvec (factor (100))Note: The following implements generators, eliminating the need of declaring arbitrarily longint arrays for caching.
MODE YIELDINT = PROC(INT)VOID;PROC gen factors = (INT n, YIELDINT yield)VOID: ( FOR i FROM 1 TO ENTIER sqrt(n) DO IF n MOD i = 0 THEN yield(i); INT other = n OVER i; IF i NE other THEN yield(n OVER i) FI FI OD);[]INT nums2factor = (45, 53, 64);FOR i TO UPB nums2factor DO INT num = nums2factor[i]; STRING sep := ": "; print(num);# FOR INT j IN # gen factors(num, # ) DO ( ### (INT j)VOID:( print((sep,whole(j,0))); sep:=", "# OD # )); print(new line)OD
+45: 1, 45, 3, 15, 5, 9 +53: 1, 53 +64: 1, 64, 2, 32, 4, 16, 8
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.
1 has 1 factors: 12 has 2 factors: 1 23 has 2 factors: 1 34 has 3 factors: 1 2 4...96 has 12 factors: 1 2 3 4 6 8 12 16 24 32 48 9697 has 2 factors: 1 9798 has 6 factors: 1 2 7 14 49 9899 has 6 factors: 1 3 9 11 33 99100 has 9 factors: 1 2 4 5 10 20 25 50 100
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.)
BEGINCOMMENT 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");ENDNUMBER TO FACTOR (OR 0 TO QUIT):-> 96THE FACTORS ARE: 2 3 4 6 8 12 16 24 32 48NUMBER TO FACTOR (OR 0 TO QUIT):-> 97THE FACTORS ARE: NONE - THE NUMBER IS PRIME.NUMBER TO FACTOR (OR 0 TO QUIT):-> 98THE FACTORS ARE: 2 7 14 49NUMBER TO FACTOR (OR 0 TO QUIT):-> 0GOODBYE
factors←{(0=(⍳⍵)|⍵)/⍳⍵}factors12345135158232469411512345factors7201234568910121516182024303640454860728090120144180240360720
> (λn. (λk. n|k=0) #. ⍳ 1 n 1) 60Vec 12 [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
-- integerFactors :: Int -> [Int]onintegerFactors(n)ifn=1then{1}elseif1>nthenmissing valueelsesetrealRootton^(1/2)setintRoottorealRootasintegersetblnPerfectSquaretointRoot=realRoot-- isFactor :: Int -> BoolscriptisFactoron|λ|(x)(nmodx)=0end|λ|endscript-- Factors up to square root of n,setlowstofilter(isFactor,enumFromTo(1,intRoot))-- integerQuotient :: Int -> IntscriptintegerQuotienton|λ|(x)(n/x)asintegerend|λ|endscript-- and quotients of these factors beyond the square root.lows&map(integerQuotient,¬items(1+(blnPerfectSquareasinteger))thru-1ofreverseoflows)endifendintegerFactors--------------------------- TEST -------------------------onrunintegerFactors(120)--> {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120}endrun-------------------- GENERIC FUNCTIONS --------------------- enumFromTo :: Int -> Int -> [Int]onenumFromTo(m,n)ifn<mthensetdto-1elsesetdto1endifsetlstto{}repeatwithifrommtonbydsetendoflsttoiendrepeatreturnlstendenumFromTo-- filter :: (a -> Bool) -> [a] -> [a]onfilter(f,xs)tellmReturn(f)setlstto{}setlngtolengthofxsrepeatwithifrom1tolngsetvtoitemiofxsif|λ|(v,i,xs)thensetendoflsttovendrepeatreturnlstendtellendfilter-- map :: (a -> b) -> [a] -> [b]onmap(f,xs)tellmReturn(f)setlngtolengthofxssetlstto{}repeatwithifrom1tolngsetendoflstto|λ|(itemiofxs,i,xs)endrepeatreturnlstendtellendmap-- Lift 2nd class handler function into 1st class script wrapper-- mReturn :: Handler -> ScriptonmReturn(f)ifclassoffisscriptthenfelsescriptproperty|λ|:fendscriptendifendmReturn
{1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120}
onfactors(n)setoutputto{}setsqrtton^0.5setlimittosqrtdiv1if(limit=sqrt)thensetendofoutputtolimitsetlimittolimit-1endifrepeatwithifromlimitto1by-1if(nmodiis0)thensetbeginningofoutputtoisetendofoutputtondiviendifendrepeatreturnoutputendfactorsfactors(123456789)
{1,3,9,3607,3803,10821,11409,32463,34227,13717421,41152263,123456789}
(= 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)))
'((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))
/* 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 */.dataszMessDeb: .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 calliNumber: .int 32767iAdrszCarriageReturn: .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 loop1: @ 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 affichageMess2: add r6,#1 @ add 1 to loop counter cmp r6,r5 @ <= number ? ble 1b @ yes loop100: pop {r1-r6} /* restaur others registers */ pop {fp,lr} /* restaur des 2 registres */ bx lr /* return */iAdrsMessValeur: .int sMessValeuriAdrszMessDeb: .int szMessDebiAdrsMessFactor: .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 2f1: 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 0x66666667factors:$[num][select1..num[x][(num%x)=0]]printfactors36
1 2 3 4 6 9 12 18 36
int[]n={11,21,32,45,67,519};for(varj:n){write(j,suffix=none);write(" =>",suffix=none);for(inti=1;i<(j/2);++i){if(j%i==0){write(" ",i,suffix=none);}}write(" ",j);}
11 => 1 1121 => 1 3 7 2132 => 1 2 4 8 3245 => 1 3 5 9 15 4567 => 1 67519 => 1 3 173 519
msgbox,%factors(45)"`n"factors(53)"`n"factors(64)Factors(n){Loop,%floor(sqrt(n)){v:=A_Index=1?1","n:mod(n,A_Index)?v:v","A_Index","n//A_Index}Sort,v,NUD,Return,v}
1,3,5,9,15,451,531,2,4,8,16,32,64
;AutoIt Version: 3.2.10.0$num=45MsgBox(0,"Factors","Factors of "&$num&" are: "&factors($num))consolewrite("Factors of "&$num&" are: "&factors($num))Funcfactors($intg)$ls_factors=""For$i=1to$intg/2if($intg/$i-int($intg/$i))=0Then$ls_factors=$ls_factors&$i&", "EndIfNextReturn$ls_factors&$intgEndFunc
Factors of 45 are: 1, 3, 5, 9, 15, 45
# syntax: GAWK -f FACTORS_OF_AN_INTEGER.AWKBEGIN{print("enter a number or C/R to exit")}{if($0==""){exit(0)}if($0!~/^[0-9]+$/){printf("invalid: %s\n",$0)next}n=$0printf("factors of %s:",n)for(i=1;i<=n;i++){if(n%i==0){printf(" %d",i)}}printf("\n")}
enter a number or C/R to exitinvalid: -1factors of 0:factors of 1: 1factors of 2: 1 2factors of 11: 1 11factors of 64: 1 2 4 8 16 32 64factors of 100: 1 2 4 5 10 20 25 50 100factors of 32766: 1 2 3 6 43 86 127 129 254 258 381 762 5461 10922 16383 32766factors of 32767: 1 7 31 151 217 1057 4681 32767
TheFactors_of_an_integer#Sinclair ZX81 BASIC code works the same in Applesoft BASIC.
REM Factors of an integerPRINT"Enter an integer";LOOP:INPUTNIFN=0THENLOOP:NA=ABS(N)NDIV2=NA/2FORI=1TONDIV2NMODI=NAMODIIFNMODI=0THENPRINTI;ENDIFNEXTIPRINTNAEND
Enter an integer?60 1 2 3 4 5 6 10 12 15 20 30 60
subroutine printFactors(n) print n; " => "; for i = 1 to n / 2 if n mod i = 0 then print i; " "; next i print nend subroutinecall printFactors(11)call printFactors(21)call printFactors(32)call printFactors(45)call printFactors(67)call printFactors(96)end
INSTALL@lib$+"SORTLIB"sort%=FN_sortinit(0,0)PRINT"The factors of 45 are "FNfactorlist(45)PRINT"The factors of 12345 are "FNfactorlist(12345)ENDDEFFNfactorlist(N%)LOCALC%,I%,L%(),L$DIML%(32)FORI%=1TOSQR(N%)IF(N%MODI%=0)THENL%(C%)=I%C%+=1IF(N%<>I%^2)THENL%(C%)=(N%DIVI%)C%+=1ENDIFENDIFNEXTI%CALLsort%,L%(0)FORI%=0TOC%-1L$+=STR$(L%(I%))+", "NEXT=LEFT$(LEFT$(L$))
The factors of 45 are 1, 3, 5, 9, 15, 45The factors of 12345 are 1, 3, 5, 15, 823, 2469, 4115, 12345
10cls20printfactors(11)30printfactors(21)40printfactors(32)50printfactors(45)60printfactors(67)70printfactors(96)80end100subprintfactors(n)110ifn<1thenprintfactors=0120printn"=> ";130fori=1ton/2140ifnmodi=0thenprinti" ";150nexti160printn170endsub
doinput"enter an integer",nloopn=0leta=abs(n)fori=1toint(a/2)ifa=int(a/i)*ithenprintiendifnextiprinta
?601 2 3 4 5 6 10 12 15 20 30 60
' FB 1.05.0 Win64SubprintFactors(nAsInteger)Ifn<1ThenReturnPrintn;" =>";ForiAsInteger=1Ton/2IfnModi=0ThenPrinti;" ";NextiPrintnEndSubprintFactors(11)printFactors(21)printFactors(32)printFactors(45)printFactors(67)printFactors(96)PrintPrint"Press any key to quit"Sleep
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
window 1, @"Factors of an Integer", (0,0,1000,270)clear local modelocal 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 nextend fn = factorStrprint @"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
Factors of 25 are: 1, 5, 25Factors of 45 are: 1, 3, 5, 9, 15, 45Factors of 103 are: 1, 103Factors of 760 are: 1, 2, 4, 5, 8, 10, 19, 20, 38, 40, 76, 95, 152, 190, 380, 760Factors of 12345 are: 1, 3, 5, 15, 823, 2469, 4115, 12345Factors of 32766 are: 1, 2, 3, 6, 43, 86, 127, 129, 254, 258, 381, 762, 5461, 10922, 16383, 32766Factors of 32767 are: 1, 7, 31, 151, 217, 1057, 4681, 32767Factors of 57097 are: 1, 57097Factors 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, 12345678Factors of 32434243 are: 1, 307, 105649, 32434243
PublicSubMain()printFactors(11)printFactors(21)printFactors(32)printFactors(45)printFactors(67)printFactors(96)EndSubprintFactors(nAsInteger)Ifn<1ThenReturnPrintn;" =>";ForiAsInteger=1Ton/2IfnModi=0ThenPrinti;" ";NextPrintnEndSub
10INPUT"Enter an integer: ",N20IFN=0THENGOTO1030NA=ABS(N)40FORI=1TONA/250IFNAMODI=0THENPRINTI;60NEXTI70PRINTNA
Enter an integer: 1 1Enter an integer: 12 1 2 3 4 6 12Enter an integer: 13 1 13Enter an integer: -22222 1 2 41 82 271 542 11111 22222
100PROGRAM"Factors.bas"110INPUTPROMPT"Number: ":N120FORI=1TOINT(N/2)130IFMOD(N,I)=0THENPRINTI;140NEXT150PRINTN
num = 10677106534462215678539721403561279maxnFactors = 1000dim primeFactors(maxnFactors), nPrimeFactors(maxnFactors)global nDifferentPrimeNumbersFound, nFactors, iFactorprint "Start finding all factors of ";num; ":"nDifferentPrimeNumbersFound=0dummy = factorize(num,2)nFactors = showPrimeFactors(num)dim factors(nFactors)dummy = generateFactors(1,1)sort factors(), 0, nFactors-1for i=1 to nFactors print i;" ";factors(i-1)next iprint "done"waitfunction 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 ifend functionfunction 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 iend functionfunction 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 ifend function
Start finding all factors of 10677106534462215678539721403561279:10677106534462215678539721403561279 = 29269^1 * 32579^1 * 98731^2 * 104729^31 12 292693 325794 987315 1047296 9535547517 28897576398 30653131019 321655724910 341196609111 974781036112 1033999889913 1096816344114 9414541412098115 9986483551747916 28530866145610917 30264142777483118 31757391375101919 32102717575462920 33686682413052121 35733179674433922 102087843129716923 108289774469337124 114868478901248925 929507088157857511126 985975507547621914927 1045874435891005819128 2988009080563683946129 3169533408943027579930 3325919841323046885131 3362085508960654054132 3527972562436533380933 3742300174123787913134 10691557723132121220135 11341079790399205145936 97346347835684259279991937 103260228929954895525562138 109533383796429148428523939 312931202998354055991106940 331942064385194335415347141 348320259061921377229637942 369481038491415704448276143 1119716148785903923259852944 10194985662483376790134271695145 10814340515605246253496593170946 32772971958814621929892634530147 36479232411295963915882747629148 10677106534462215678539721403561279done
This is a somewhat simpler approach for finding the factors of smaller numbers (less than one million).
print "ROSETTA CODE - Factors of an integer"'A simpler approach for smaller numbers[Start]printinput "Enter an integer (< 1,000,000): "; nn=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 printend selectgoto [Start][Quit]print "Program complete."endfunction 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 yend function
ROSETTA CODE - Factors of an integerEnter an integer (< 1,000,000): 1The factor of 1 is: 1Enter an integer (< 1,000,000): 2The 2 factors of 2 are: 1 2 (Prime)Enter an integer (< 1,000,000): 4The 3 factors of 4 are: 1 2 4Enter an integer (< 1,000,000): 6The 4 factors of 6 are: 1 2 3 6Enter an integer (< 1,000,000): 999999The 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 999999Enter an integer (< 1,000,000):Program complete.
10REM Factors of an integer20PRINT"Enter an integer";30INPUTN40IFN=0THEN3050N1=ABS(N)60FORI=1TON1/270IFINT(N1/I)*I<>N1THEN9080PRINTI;90NEXTI100PRINTN1110END
10INPUT"Enter an integer: ";N20IFN=0THENGOTO1030N1=ABS(N)40FORI=1TON1/250IFN1MODI=0THENPRINTI;60NEXTI70PRINTN1
10REM Factors of an integer20INPUT"Enter an integer";N30IFN=0THEN2040NA=ABS(N)50FORI=1TOINT(NA/2)60IFNA=INT(NA/I)*ITHENPRINTI;70NEXTI80PRINTNA90END
Enter an integer? 60 1 2 3 4 5 6 10 12 15 20 30 60
See alsoMinimal BASIC
10REM FACTORS OF AN INTEGER20INPUT"ENTER AN INTEGER"N30IFN=0GOTO2040LETA=ABS(N)50IFA=1GOTO9060FORI=1TOA/270IF(A/I)*I=APRINTI," ",80NEXTI90PRINTA100STOP
3 runs.
ENTER AN INTEGER:1 1
ENTER AN INTEGER:60 1 2 3 4 5 6 10 12 15 20 30 60
ENTER AN INTEGER:-22222 1 2 41 82 271 542 11111 22222
ProcedurePrintFactors(n)Protectedi,lim=Round(sqr(n),#PB_Round_Up)NewListF.i()Fori=1TolimIfn%i=0AddElement(F()):F()=iAddElement(F()):F()=n/iEndIfNext;-PresenttheresultSortList(F(),#PB_Sort_Ascending)ForEachF()Print(str(F())+" ")NextEndProcedureIfOpenConsole()Print("Enter integer to factorize: ")PrintFactors(Val(Input()))Print(#CRLF$+#CRLF$+"Press ENTER to quit."):Input()EndIf
Enter integer to factorize: 96 1 2 3 4 6 8 12 16 24 32 48 96
'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 IntegerRandomize TimerDividendum = Int(Rnd * 1000) + 1Print " Dividendum: "; DividendumIndex = Int(Dividendum / 2)print "Divisors: ";While Index > 0 If Dividendum Mod Index = 0 Then Print Index; " "; Index = Index - 1WendEnd
SeeQuickBASIC.
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).
DECLARESUBfactor(whatASINTEGER)REDIMSHAREDfactors(0)ASINTEGERDIMiASINTEGER,LASINTEGERINPUT"Gimme a number";ifactoriPRINTfactors(0);FORL=1TOUBOUND(factors)PRINT",";factors(L);NEXTPRINTSUBfactor(whatASINTEGER)DIMtmpint1ASINTEGERDIML0ASINTEGER,L1ASINTEGERREDIMtmp(0)ASINTEGERREDIMfactors(0)ASINTEGERfactors(0)=1FORL0=2TOwhatIF(0=(whatMODL0))THEN'all this REDIMing and copying can be replaced with:'REDIM PRESERVE factors(UBOUND(factors)+1)'in languages that support the PRESERVE keywordREDIMtmp(UBOUND(factors))ASINTEGERFORL1=0TOUBOUND(factors)tmp(L1)=factors(L1)NEXTREDIMfactors(UBOUND(factors)+1)ASINTEGERFORL1=0TOUBOUND(factors)-1factors(L1)=tmp(L1)NEXTfactors(UBOUND(factors))=L0ENDIFNEXTENDSUB
Gimme a number? 17 1 , 17 Gimme a number? 12345 1 , 3 , 5 , 15 , 823 , 2469 , 4115 , 12345 Gimme a number? 32765 1 , 5 , 6553 , 32765 Gimme a number? 32766 1 , 2 , 3 , 6 , 43 , 86 , 127 , 129 , 254 , 258 , 381 , 762 , 5461 , 10922 , 16383 , 32766
10INPUT"Enter an integer: ";N20IFN=0THENGOTO1530N1=ABS(N)40FORI=1TON1/250IFN1-INT(N1/I)*I=0THENPRINTI;" ";60NEXTI70PRINTN1
Functionfactors(numAsUInt64)AsUInt64()'This function accepts an unsigned 64 bit integer as input and returns an array of unsigned 64 bit integersDimresult()AsUInt64DimiFactorAsUInt64=1WhileiFactor<=num/2'Since a factor will never be larger than half of the numberIfnumModiFactor=0Thenresult.Append(iFactor)EndIfiFactor=iFactor+1Wendresult.Append(num)'Since a given number is always a factor of itselfReturnresultEndFunction
PRINT"Factors of 45 are ";factorlist$(45)PRINT"Factors of 12345 are ";factorlist$(12345)ENDFUNCTIONfactorlist$(f)DIML(100)FORi=1TOSQR(f)IF(fMODi)=0THENL(c)=ic=c+1IF(f<>i^2)THENL(c)=(f/i)c=c+1ENDIFENDIFNEXTis=1WHILEs=1s=0FORi=0TOc-1IFL(i)>L(i+1)ANDL(i+1)<>0THENt=L(i)L(i)=L(i+1)L(i+1)=ts=1ENDIFNEXTiWENDFORi=0TOc-1factorlist$=factorlist$+STR$(L(i))+", "NEXTENDFUNCTION
Factors of 45 are 1, 3, 5, 9, 15, 45, Factors of 12345 are 1, 3, 5, 15, 823, 2469, 4115, 12345,
10INPUTN20FORI=1TON30IFN/I=INT(N/I)THENPRINTI;" ";40NEXTI
315
1 3 5 7 9 15 35 45 63 105 315
100PRINT"Give me a number:"110INPUTI120LETC=1130PRINT"Factors of ",I,":"140IFI/C*C=ITHENPRINTC150LETC=C+1160IFC<=ITHENGOTO140170END
Give me a number:60Factors of 60:123456101215203060
SUBprintfactors(n)IFn<1THENEXITSUBPRINTn;"=>";FORi=1TOn/2IFREMAINDER(n,i)=0THENPRINTi;NEXTiPRINTnENDSUBCALLprintfactors(11)CALLprintfactors(21)CALLprintfactors(32)CALLprintfactors(45)CALLprintfactors(67)CALLprintfactors(96)END
FunctionFactors(xAsInteger)AsStringApplication.VolatileDimiAsIntegerDimcooresponding_factorsAsStringFactors=1corresponding_factors=xFori=2ToSqr(x)IfxModi=0ThenFactors=Factors&", "&iIfi<>x/iThencorresponding_factors=x/i&", "&corresponding_factorsEndIfNextiIfx<>1ThenFactors=Factors&", "&corresponding_factorsEndFunction
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"
PROGRAM"Factors of an integer"VERSION"0.0000"DECLAREFUNCTIONEntry()DECLAREFUNCTIONprintFactors(n)FUNCTIONEntry()printFactors(11)printFactors(21)printFactors(32)printFactors(45)printFactors(67)printFactors(96)ENDFUNCTIONFUNCTIONprintFactors(n)PRINTn;" =>";FORi=1TOn/2IFnMODi=0THENPRINTi;" ";NEXTiPRINTnENDFUNCTIONENDPROGRAM
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 nend sub printFactors(11)printFactors(21)printFactors(32)printFactors(45)printFactors(67)printFactors(96)printend
10INPUT"Enter a number or 0 to exit: ";n20IFn=0THENSTOP30PRINT"Factors of ";n;": ";40FORi=1TOn50IFFNm(n,i)=0THENPRINTi;" ";60NEXTi70DEF FNm(a,b)=a-INT(a/b)*b
Command line version:
@echo offsetres=Factors of%1:for/L%%iin(1,1,%1)docall:fac%1%%iecho%res%goto:eof:facset/atest=%1%%%2if%test%equ 0setres=%res%%2
>factors 32767Factors of 32767: 1 7 31 151 217 1057 4681 32767>factors 45Factors of 45: 1 3 5 9 15 45>factors 53Factors of 53: 1 53>factors 64Factors of 64: 1 2 4 8 16 32 64>factors 100Factors of 100: 1 2 4 5 10 20 25 50 100
Interactive version:
@echo offset/plimit=Gimme a number:setres=Factors of%limit%:for/L%%iin(1,1,%limit%)docall:fac%limit%%%iecho%res%goto:eof:facset/atest=%1%%%2if%test%equ 0setres=%res%%2
>factorsGimme a number:27Factors of 27: 1 3 9 27>factorsGimme a number:102Factors of 102: 1 2 3 6 17 34 51 102
/* Calculate the factors of n and return their count. * This function mutates the global array f[] which will * contain all factors of n in ascending order after the call! */define f(n){auto i, d, h, h[], l, o/* Local variables: * i: Loop variable. * d: Complementary (higher) factor to i. * h: Will always point to the last element of h[]. * h[]: Array to hold the greater factor of the pair (x, y), where * x * y == n. The factors are stored in descending order. * l: Will always point to the next free spot in f[]. * o: For saving the value of scale. *//* Use integer arithmetic */ o=scalescale=0/* Two factors are 1 and n (if n != 1) */ f[l++]=1if(n==1)return(1) h[0]= n/* Main loop */for(i=2; i< h[h]; i++){if(n% i==0){ d= n/ iif(d!= i){ h[++h]= d} f[l++]= i}}/* Append the values in h[] to f[] */while(h>=0){ f[l++]= h[h--]}scale= oreturn(l)}
10:p&v:>:0:g%#v_0:g\:0:g/\v>:0:g:*`|>>0:g1+0:p>:0:g:*-#v_0:g\>$>:!#@_.v>^^," "<
A bqncrate idiom.
Factors←(1+↕)⊸(⊣/˜0=|)•ShowFactors12345•ShowFactors729
⟨ 1 3 5 15 823 2469 4115 12345 ⟩⟨ 1 3 9 27 81 243 729 ⟩
Theprimes library from bqn-libs can be used for a solution that's more efficient for large inputs.FactorExponents returns each unique prime factor along with its exponent.
⟨FactorExponents⟩←•Import"primes.bqn"# With appropriate pathFactors←{∧⥊1×⌜´⋆⟜(↕1+⊢)¨˝FactorExponents𝕩}
blsq ) 32767 fc{1 7 31 151 217 1057 4681 32767}#include<stdio.h>#include<stdlib.h>typedefstruct{int*list;shortcount;}Factors;voidxferFactors(Factors*fctrs,int*flist,intflix){intix,ij;intnewSize=fctrs->count+flix;if(newSize>flix){fctrs->list=realloc(fctrs->list,newSize*sizeof(int));}else{fctrs->list=malloc(newSize*sizeof(int));}for(ij=0,ix=fctrs->count;ix<newSize;ij++,ix++){fctrs->list[ix]=flist[ij];}fctrs->count=newSize;}Factors*factor(intnum,Factors*fctrs){intflist[301],flix;intdvsr;flix=0;fctrs->count=0;free(fctrs->list);fctrs->list=NULL;for(dvsr=1;dvsr*dvsr<num;dvsr++){if(num%dvsr!=0)continue;if(flix==300){xferFactors(fctrs,flist,flix);flix=0;}flist[flix++]=dvsr;flist[flix++]=num/dvsr;}if(dvsr*dvsr==num)flist[flix++]=dvsr;if(flix>0)xferFactors(fctrs,flist,flix);returnfctrs;}intmain(intargc,char*argv[]){intnums2factor[]={2059,223092870,3135,45};Factorsftors={NULL,0};charsep;inti,j;for(i=0;i<4;i++){factor(nums2factor[i],&ftors);printf("\nfactors of %d are:\n ",nums2factor[i]);sep=' ';for(j=0;j<ftors.count;j++){printf("%c %d",sep,ftors.list[j]);sep=',';}printf("\n");}return0;}
#include<stdio.h>#include<stdlib.h>#include<string.h>/* 65536 = 2^16, so we can factor all 32 bit ints */charbits[65536];typedefunsignedlongulong;ulongprimes[7000],n_primes;typedefstruct{ulongp,e;}prime_factor;/* prime, exponent */voidsieve(){inti,j;memset(bits,1,65536);bits[0]=bits[1]=0;for(i=0;i<256;i++)if(bits[i])for(j=i*i;j<65536;j+=i)bits[j]=0;/* collect primes into a list. slightly faster this way if dealing with large numbers */for(i=j=0;i<65536;i++)if(bits[i])primes[j++]=i;n_primes=j;}intget_prime_factors(ulongn,prime_factor*lst){ulongi,e,p;intlen=0;for(i=0;i<n_primes;i++){p=primes[i];if(p*p>n)break;for(e=0;!(n%p);n/=p,e++);if(e){lst[len].p=p;lst[len++].e=e;}}returnn==1?len:(lst[len].p=n,lst[len].e=1,++len);}intulong_cmp(constvoid*a,constvoid*b){return*(constulong*)a<*(constulong*)b?-1:*(constulong*)a>*(constulong*)b;}intget_factors(ulongn,ulong*lst){intn_f,len,len2,i,j,k,p;prime_factorf[100];n_f=get_prime_factors(n,f);len2=len=lst[0]=1;/* L = (1); L = (L, L * p**(1 .. e)) forall((p, e)) */for(i=0;i<n_f;i++,len2=len)for(j=0,p=f[i].p;j<f[i].e;j++,p*=f[i].p)for(k=0;k<len2;k++)lst[len++]=lst[k]*p;qsort(lst,len,sizeof(ulong),ulong_cmp);returnlen;}intmain(){ulongfac[10000];intlen,i,j;ulongnums[]={3,120,1024,2UL*2*2*2*3*3*3*5*5*7*11*13*17*19};sieve();for(i=0;i<4;i++){len=get_factors(nums[i],fac);printf("%lu:",nums[i]);for(j=0;j<len;j++)printf(" %lu",fac[j]);printf("\n");}return0;}
3: 1 3120: 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 1201024: 1 2 4 8 16 32 64 128 256 512 10243491888400: 1 2 3 4 5 6 7 8 9 10 11 ...(>1900 numbers)... 1163962800 1745944200 3491888400
staticvoidMain(string[]args){do{Console.WriteLine("Number:");Int64p=0;do{try{p=Convert.ToInt64(Console.ReadLine());break;}catch(Exception){}}while(true);Console.WriteLine("For 1 through "+((int)Math.Sqrt(p)).ToString()+"");for(intx=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);}
Number:32434243For 1 through 5695Found: 1. 32434243 / 1 = 32434243Found: 307. 32434243 / 307 = 105649Done.
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;publicstaticclassExtension{publicstaticList<int>Factors(thisintme){returnEnumerable.Range(1,me).Where(x=>me%x==0).ToList();}}classProgram{staticvoidMain(string[]args){Console.WriteLine(String.Join(", ",45.Factors()));}}
1, 3, 5, 9, 15, 45
#include<iostream>#include<iomanip>#include<vector>#include<algorithm>#include<iterator>std::vector<int>GenerateFactors(intn){std::vector<int>factors={1,n};for(inti=2;i*i<=n;++i){if(n%i==0){factors.push_back(i);if(i*i!=n)factors.push_back(n/i);}}std::sort(factors.begin(),factors.end());returnfactors;}intmain(){constintSampleNumbers[]={3135,45,60,81};for(size_ti=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;}returnEXIT_SUCCESS;}
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
sharedvoidrun(){{Integer*}getFactors(Integern)=>(1..n).filter((Integerelement)=>element.divides(n));for(Integeriin1..100){print("the factors of ``i`` are ``getFactors(i)``");}}
Inspired by the Clojure solution:
iterfactors(n){foriin1..floor(sqrt(n)):int{ifn%i==0then{yieldi;yieldn/i;}}}
(defnfactors[n](filter#(zero?(remn%))(range1(incn))))(print(factors45))
(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.
(defnfactors[n](into(sorted-set)(mapcat(fn[x][x(/nx)])(filter#(zero?(remn%))(range1(inc(Math/sqrtn)))))))
Same idea, using for comprehensions.
(defnfactors[n](into(sorted-set)(reduceconcat(for[x(range1(inc(Math/sqrtn))):when(zero?(remnx))][x(/nx)]))))
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 isqrtfactors = 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 factorsstart_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, "") endend start_up
Factors of 3135: 1 3 1045 5 627 11 285 15 209 19 165 33 95 55 57 3135Factors of 45: 1 3 15 5 9 45Factors of 64: 1 2 32 4 16 8 64Factors of 53: 1 53Factors of 45: 1 3 15 5 9 45Factors of 81: 1 3 27 9 81
IDENTIFICATIONDIVISION.PROGRAM-ID.FACTORS.DATADIVISION.WORKING-STORAGESECTION.01CALCULATING.03NUMUSAGEBINARY-LONGVALUEZERO.03LIMUSAGEBINARY-LONGVALUEZERO.03CNTUSAGEBINARY-LONGVALUEZERO.03DIVUSAGEBINARY-LONGVALUEZERO.03REMUSAGEBINARY-LONGVALUEZERO.03ZRSUSAGEBINARY-SHORTVALUEZERO.01DISPLAYING.03DISPIC 9(10)USAGEDISPLAY.PROCEDUREDIVISION.MAIN-PROCEDURE.DISPLAY"Factors of? "WITHNOADVANCINGACCEPTNUMDIVIDENUMBY2GIVINGLIM.PERFORMVARYINGCNTFROM1BY1UNTILCNT>LIMDIVIDENUMBYCNTGIVINGDIVREMAINDERREMIFREM=0MOVECNTTODISPERFORMSHODISEND-IFEND-PERFORM.MOVENUMTODIS.PERFORMSHODIS.STOPRUN.SHODIS.MOVEZEROTOZRS.INSPECTDISTALLYINGZRSFORLEADINGZERO.DISPLAYDIS(ZRS+1:)EXITPARAGRAPH.ENDPROGRAMFACTORS.
# Reference implementation for finding factors is slow, but hopefully# robust--we'll use it to verify the more complicated (but hopefully faster)# algorithm.slow_factors=(n) ->(iforiin[1..n]whenn%i==0)# The rest of this code does two optimizations:# 1) When you find a prime factor, divide it out of n (smallest_prime_factor).# 2) Find the prime factorization first, then compute composite factors from those.smallest_prime_factor=(n) ->foriin[2..n]returnnifi*i>nreturniifn%i==0prime_factors=(n) ->return{}ifn==1spf=smallest_prime_factornresult=prime_factors(n/spf)result[spf]or=0result[spf]+=1resultfast_factors=(n) ->prime_hash=prime_factorsnexponents=[]forpofprime_hashexponents.pushp:pexp:0result=[]whiletruefactor=1forobjinexponentsfactor*=Math.powobj.p,obj.expresult.pushfactorbreakiffactor==n# roll the odometerforobj,iinexponentsifobj.exp<prime_hash[obj.p]obj.exp+=1breakelseobj.exp=0returnresult.sort(a, b) ->a-bverify_factors=(factors, n) ->expected_result=slow_factorsnthrowError("wrong length")iffactors.length!=expected_result.lengthforfactor,iinexpected_resultconsole.logError("wrong value")iffactors[i]!=factorfornin[1,3,4,8,24,37,1001,11111111111,99999999999]factors=fast_factorsnconsole.logn,factorsifn<1000000verify_factorsfactors,n
> coffee factors.coffee 1 [ 1 ]3 [ 1, 3 ]4 [ 1, 2, 4 ]8 [ 1, 2, 4, 8 ]24 [ 1, 2, 3, 4, 6, 8, 12, 24 ]37 [ 1, 37 ]1001 [ 1, 7, 11, 13, 77, 91, 143, 1001 ]11111111111 [ 1, 21649, 513239, 11111111111 ]99999999999 [ 1, 3, 9, 21649, 64947, 194841, 513239, 1539717, 4619151, 11111111111, 33333333333, 99999999999 ]
We iterate in the range1..sqrt(n) collecting ‘low’ factors and corresponding ‘high’ factors, and combine at the end to produce an ordered list of factors.
(defunfactors(n&aux(lows'())(highs'()))(do((limit(1+(isqrtn)))(factor1(1+factor)))((=factorlimit)(when(=n(*limitlimit))(pushlimithighs))(remove-duplicates(nreconclowshighs)))(multiple-value-bind(quotientremainder)(floornfactor)(when(zeropremainder)(pushfactorlows)(pushquotienthighs)))))
Brute force and slow, by checking every value up to n.
structIntdeffactors()(1..self).select{|n|(self%n).zero?}endend
Faster, by only checking values up to.
structIntdeffactorsf=[]ofInt32(1..Math.sqrt(self)).each{|i|(f<<i;f<<self//iifself//i!=i)if(self%i).zero?}f.sortendend
Tests:
[45,53,64].each{|n|puts"#{n} :#{n.factors}"}
45 : [1, 3, 5, 9, 15, 45]53 : [1, 53]64 : [1, 2, 4, 8, 16, 32, 64]
importstd.stdio,std.math,std.algorithm;T[]factors(T)(inTn)purenothrow{if(n==1)return[n];T[]res=[1,n];Tlimit=cast(T)real(n).sqrt+1;for(Ti=2;i<limit;i++){if(n%i==0){res~=i;immutableq=n/i;if(q>i)res~=q;}}returnres.sort().release;}voidmain(){writefln("%(%s\n%)",[45,53,64,1111111].map!factors);}
[1, 3, 5, 9, 15, 45][1, 53][1, 2, 4, 8, 16, 32, 64][1, 239, 4649, 1111111]
importstd.stdio,std.algorithm,std.range;autofactors(I)(In){returniota(1,n+1).filter!(i=>n%i==0);}voidmain(){36.factors.writeln;}
[1, 2, 3, 4, 6, 9, 12, 18, 36]
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));}[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
Factors of 998877 are: 1 3 11 33 30269 90807 332959 9988770m1.120s
[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
0m0.004s
See#Pascal.
DuckDB allows both functional and table-oriented approaches to solvingproblems such as finding the factors of a number, and solutions usingboth approaches are presented here.
The following function produces a list of the sorted factors.
createorreplacefunctionfactors(n)aslist_filter(generate_series(1,sqrt(n)::INT),i->n%i=0).list_transform(i->if(n//i=i,[i],[i,n//i])).flatten().list_sort();##Examplesselectn,factors(n)from(selectunnest([1,2,3,4,5,6,45,53,64])asn);
┌───────┬──────────────────────────┐│ n │ factors(n) ││ int32 │ int64[] │├───────┼──────────────────────────┤│ 1 │ [1] ││ 2 │ [1, 2] ││ 3 │ [1, 3] ││ 4 │ [1, 2, 4] ││ 5 │ [1, 5] ││ 6 │ [1, 2, 3, 6] ││ 45 │ [1, 3, 5, 9, 15, 45] ││ 53 │ [1, 53] ││ 64 │ [1, 2, 4, 8, 16, 32, 64] │└───────┴──────────────────────────┘
The following function produces a table of the factors without sorting them.
createorreplacefunctionunsorted_factors(n)astable(withcteas(selectifromgenerate_series(1,sqrt(n)::INT)_(i)wheren%i=0)fromcteunionall(selectn//ifromctewheren//i!=i));##Examplesfromunsorted_factors(99);selectn,(selectarray_agg(x)fromunsorted_factors(n)_(x))asunsorted_factorsfrom(selectunnest([1,2,3,4,5,6,45,53,64])asn);
┌───────┐│ i ││ int64 │├───────┤│ 1 ││ 3 ││ 9 ││ 99 ││ 33 ││ 11 │└───────┘┌───────┬──────────────────────────┐│ n │ factors ││ int32 │ int64[] │├───────┼──────────────────────────┤│ 1 │ [1] ││ 2 │ [2, 1] ││ 3 │ [3, 1] ││ 4 │ [4, 1, 2] ││ 5 │ [1, 5] ││ 6 │ [6, 3, 1, 2] ││ 45 │ [45, 15, 9, 1, 3, 5] ││ 53 │ [53, 1] ││ 64 │ [1, 2, 4, 8, 64, 32, 16] │└───────┴──────────────────────────┘
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)}Output:
13591545
This example isin need of improvement:
|
def factors(x :(int > 0)) { var xfactors := [] for f ? (x % f <=> 0) in 1..x { xfactors with= f } return xfactors}n = 720for i = 1 to n if n mod i = 0 factors[] &= i ..print factors[]
prime-factors gives the list of n's prime-factors. We mix them to get all the factors.
;; ppows;; input : a list g of grouped prime factors ( 3 3 3 ..);; returns (1 3 9 27 ...)(define(ppowsg(mult1))(for/fold(ppows'(1))((ag))(set!mult(*multa))(consmultppows)));; factors;; decomp n into ((2 2 ..) ( 3 3 ..) ) prime factors groups;; combines (1 2 4 8 ..) (1 3 9 ..) lists(define(factorsn)(list-sort<(if(<=n1)'(1)(for/fold(divs'(1))((g(mapppows(group(prime-factorsn)))))(for*/list((adivs)(bg))(*ab))))))
(lib'bigint)(factors666)→(12369183774111222333666)(length(factors108233175859200))→666;; 💀(definehuge1200034005600070000008900000000000000000)(time(length(factorshuge)))→(394ms7776)
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).
[Factors of an integer, from Rosetta Code website.][EDSAC program, Initial Orders 2.][2024-12-25 (1) Fixed bug in print subroutine (2) Added factors of more integers.[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.)] T46K P600F [address of integers][Subroutine R2]GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z T#N [pass address of integers to R2][Integers, separated by 'F' and terminated by '#TZ', as R2 requires.]420F42000F420000F99999F999999F0# TZ [resume normal loading] [Modified library subroutine P7. Prints signed integer; up to 10 digits, left-justified. Input: 0D = integer 52 locations. Load at even address. Workspace 4D.] T56KGKA3FT42@A47@T31@ADE10@T31@A46@T31@SDTDH44#@NDYFLDT4DS43@TFH17@S17@A43@G23@UFS43@T1FV4DAFG48@SFLDUFXFOFFFSFL4FT4DA47@T31@A1FA43@G20@XFT44#ZPFT43ZP1024FP610D@524DO26@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.] T110KGKA3FT35@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.] T148K GK A3F [form and plant link for return] T55@ AD [load integer whose factors are to be found] T56#@ [store] A62#@ [load 1] T58#@ [possible factor := 1] S65@ [negative count of items per line] T64@ [initialize count] [Start of loop round possible factors] [8] TF [clear acc] A56#@ [load integer] T4D [to 4D for division] A58#@ [load possible factor] T6D [to 6D for division] A13@ [for return from next] G110F [do division; clears acc] A6D [save quotient (6D may be changed below)] T60#@ S4D [load negative of remainder] G44@ [skip if remainder > 0] [Here if m is a factor of n.] [Print m and the quotient together] TF [clear acc] A64@ [test count of items per line] G26@ [skip if not start of line] S65@ [start of line, reset count] T64@ O70@ [and print CR, LF] O71@ [26] TF [clear acc] O67@ [print '('] A58#@ [load factor] TD [to 0D for printing] A30@ [for return from next] G56F [print factor; clears acc] O69@ [print comma] A60#@ [load quotient] TD [to 0D for printing] A35@ [for return from next] G56F [print quotient; clears acc] O68@ [print ')'] A64@ [negative counter for items per line] A2F [inc] E43@ [skip if end of line] O66@ [not end of line, print 2 spaces] O66@ [43] T64@ [update counter] [Common code after testing possible factor] [44] TF [clear acc] A58#@ [load possible factor] A62#@ [inc by 1] U58#@ [store back] S60#@ [compare with quotient] G8@ [loop if (new factor) < (old quotient)] [Here when found all factors] O70@ [print CR, LF twice] O71@ O70@ O71@ TF [exit with acc = 0] [55] EF [(planted) return to caller] [--------------] [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 [clear whole of 35-bit constant, including sandwich bit] PF T62Z [resume normal loading] [62] PD PF [35-bit constant 1] [64] PF [negative counter for items per line] [65] P4F [items per line, in address field] [66] !F [space] [67] KF [68] LF [69] NF [comma, in figure shift] [70] @F [carriage return] [71] &F [line feed] [Main routine for demonstrating subroutine.] T400K GK [0] #F [figure shift] [1] K4096F [null char] [2] S#N [order to load negative first number] [3] P2F [to inc address by 2 for next number] [Enter with acc = 0] [4] O@ [set teleprinter to figures] A2@ [load order for first integer] [6] T7@ [plant in next order] [7] SD [load negative of 35-bit integer] E17@ [exit if number is 0] TD SD [convert to positive] TD [pass to subroutine] A12@ [call subroutine to find and print factors] G148F A7@ [modify order above, for next integer] A3@ E6@ [always jump, since S = 12 > 0] [17] O1@ [done, print null to flush printer buffer] ZF [stop] E4Z [define entry point] PF [acc = 0 on entry(1,420) (2,210) (3,140) (4,105)(5,84) (6,70) (7,60) (10,42)(12,35) (14,30) (15,28) (20,21)(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,420000) (2,210000) (3,140000) (4,105000)(5,84000) (6,70000) (7,60000) (8,52500)(10,42000) (12,35000) (14,30000) (15,28000)(16,26250) (20,21000) (21,20000) (24,17500)(25,16800) (28,15000) (30,14000) (32,13125)(35,12000) (40,10500) (42,10000) (48,8750)(50,8400) (56,7500) (60,7000) (70,6000)(75,5600) (80,5250) (84,5000) (96,4375)(100,4200) (105,4000) (112,3750) (120,3500)(125,3360) (140,3000) (150,2800) (160,2625)(168,2500) (175,2400) (200,2100) (210,2000)(224,1875) (240,1750) (250,1680) (280,1500)(300,1400) (336,1250) (350,1200) (375,1120)(400,1050) (420,1000) (480,875) (500,840)(525,800) (560,750) (600,700) (625,672)(1,99999) (3,33333) (9,11111) (41,2439)(123,813) (271,369)(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)
open listfactors m = filter (\x -> m % x == 0) [1..m]
factors m = [x \\ x <- [1..m] | m % x == 0]
defmoduleRCdodeffactor(1),do:[1]deffactor(n)do(fori<-1..div(n,2),rem(n,i)==0,do:i)++[n]end# Recursive (faster version);defdivisor(n),do:divisor(n,1,[])|>Enum.sortdefpdivisor(n,i,factors)whenn<i*i,do:factorsdefpdivisor(n,i,factors)whenn==i*i,do:[i|factors]defpdivisor(n,i,factors)whenrem(n,i)==0,do:divisor(n,i+1,[i,div(n,i)|factors])defpdivisor(n,i,factors),do:divisor(n,i+1,factors)endEnum.each([45,53,60,64],fnn->IO.puts"#{n}:#{inspectRC.factor(n)}"end)IO.puts"\nRange:#{inspectrange=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)
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..10000factor prime count : 1229, 7.316 secdivisor prime count : 1229, 0.265 sec
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 resultendfun 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 0endexit main(Runtime.args)
emal.exe Org\RosettaCode\FactorsOfAnInteger.emal 999997[1,757,1321,999997]
factors(N)->[I||I<-lists:seq(1,trunc(N/2)),NremI==0]++[N].
Another, less concise, but faster version
-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)whenK>Q->[];divisors(K,N,_Q)whenNremK=/=0->[]++divisors(K+1,N,math:sqrt(N));divisors(K,N,_Q)whenK*K==N->[K]++divisors(K+1,N,math:sqrt(N));divisors(K,N,_Q)->[K,NdivK]++divisors(K+1,N,math:sqrt(N)).
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|...]}The first number is milliseconds. I'v ommitted repeating the first fuction.
PROGRAM FACTORS!$DOUBLEPROCEDURE 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 PROCEDUREBEGIN 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 PROGRAMThe factors of 45 are 1, 3, 5, 9, 15, 45The factors of 12345 are 1, 3, 5, 15, 823, 2469, 4115, 12345
Binding the nameFACTORS to a custom function defined by the following LAMBDA expression
in the Name Manager of an Excel workbook.
(See:The LAMBDA worksheet function in Excel)
=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())))
and assuming that in the same worksheet, each of the following names is bound to the reusable generic lambda expression which follows it:
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))))
TheFACTORS function, applied to an integer, defines a column of integer values.
Here we define a row instead, by composingFACTORS with the standardTRANSPOSE function.
| fx | =TRANSPOSE(FACTORS(A2)) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | ||
| 1 | N | Factors | ||||||||||||||||
| 2 | 64 | 1 | 2 | 4 | 8 | 16 | 32 | 64 | ||||||||||
| 3 | 120 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 10 | 12 | 15 | 20 | 24 | 30 | 40 | 60 | 120 | |
| 4 | 123456789 | 1 | 3 | 9 | 3607 | 3803 | 10821 | 11409 | 32463 | 34227 | 13717421 | 41152263 | 123456789 | |||||
| 5 | 2 | 1 | 2 | |||||||||||||||
| 6 | 1 | 1 | ||||||||||||||||
| 7 | 0 | #N/A | ||||||||||||||||
| 8 | -1 | #N/A | ||||||||||||||||
If number % divisor = 0 then both divisor AND number / divisor are factors.
So, we only have to search till sqrt(number).
Also, this is lazily evaluated.
letfactorsnumber=seq{fordivisorin1..(float>>sqrt>>int)numberdoifnumber%divisor=0thenyielddivisorifnumber<>1thenyieldnumber/divisor//special case condition: when number=1 then divisor=(number/divisor), so don't repeat it}
[6;120;2048;402642;1206432]|>Seq.iter(funn->printf"%d :"n;[1..n]|>Seq.filter(fung->n%g=0)|>Seq.iter(funn->printf" %d"n);printfn"");;
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 1278 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 100536 134048 150804 201072 301608 402144 603216 1206432
USE: math.primes.factors ( scratchpad ) 24 divisors . { 1 2 3 4 6 8 12 24 }[1[\$@$@-][\$@$@$@$@\/*=[$." "]?1+]#.%]f:45f;! 53f;! 64f;!
0v>i:0(?v'0'%+a*>~a,:1:>r{% ?vr:nr','ov^:&:;?(&:+1r:<<
Must be called with pre-polulated value (Positive Integer) in the input stack. Try at Fish Playground[1].
For Input Number :
120
The following output was generated:
1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120,
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.
:factorsdup2/1+1dodupimod0=ifiswapthenloop;:.factorsfactorsbegindupdup.1<>whiledroprepeatdropcr;45.factors53.factors64.factors100.factors
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.
:sqs"dup *"evaluate;immediate:factors( n a xt -- )swap2>r1BEGIN2dupsq>WHILE2dup/modswap0=IFoverr>r@executer@execute>rELSEdropTHEN1+REPEAT2dupsq=IF2r>swapexecutenipELSE2dropr>rdropTHEN;:<with-factors>create2,does>2@factors;0:nonamenip1+;<with-factors>count-factors0'+<with-factors>sum-factors0:nonameswap.;<with-factors>(.factors):.factors(.factors)drop;
100 .factors 1 100 2 50 4 25 5 20 10 ok100 count-factors . 9 ok100 sum-factors . 217 ok1 100 + 2 + 50 + 4 + 25 + 5 + 20 + 10 + . 217 ok \ test sum-factors result77 .factors 1 77 7 11 ok108 .factors 1 108 2 54 3 36 4 27 6 18 9 12 ok
programFactorsimplicit noneinteger::i,numberwrite(*,*)"Enter a number between 1 and 2147483647"read*,numberdoi=1,int(sqrt(real(number)))-1if(mod(number,i)==0)write(*,*)i,number/iend do! Check to see if number is a squarei=int(sqrt(real(number)))if(i*i==number)then write(*,*)ielse if(mod(number,i)==0)then write(*,*)i,number/iend ifend 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.
Thefactors[n] function will return the prime decomposition ofn.
TheallFactors[n,include1=true,includeN=true,sort=true,onlyToSqrt=false] function will return all factors ofn. The optional argumentsinclude1 andincludeN indicate if the numbers 1 and n are to be included in the results. If the optional argumentsort is true, the results will be sorted. If the optional argumentonlyToSqrt=true, then only the factors less than or equal to the square root of the number will be produced.
The following produces all factors of n, including 1 and n:
allFactors[n]
Function to compute set of factors:
def factors( n ) = {d | d <- 1..n if d|n}Test:
for x <- [103, 316, 519, 639, 760] println( 'The set of factors of ' + x + ' is ' + factors(x) )
The set of factors of 103 is {1, 103}The set of factors of 316 is {158, 4, 79, 1, 2, 316}The set of factors of 519 is {1, 3, 173, 519}The set of factors of 639 is {9, 639, 71, 213, 1, 3}The set of factors of 760 is {8, 19, 4, 40, 152, 5, 10, 76, 1, 95, 190, 760, 20, 2, 38, 380}Function to compute set of factors:
local fn Factors( n as int ) as CFArrayRef CFMutableArrayRef mutArray = fn MutableArrayNew for int factor = 1 to sqr(n) if ( n mod factor == 0 ) MutableArrayAddObject( mutArray, @(factor) ) if ( n/factor != factor ) MutableArrayAddObject( mutArray, @(n/factor) ) end if end if next CFArrayRef result = fn ArraySortedArrayUsingSelector( mutArray, @"compare:" )end fn = resultmda (0) = {1,2,3,4,5,6,7,8,9,10,20,40,60,80,100,200,300,400,512,677,768,966,1000,1024,2048,4096}int i, nfor i = 0 to mda_count -1 n = mda_integer(i) print fn StringWithFormat( @"Factors of %4d: [%@]", n, fn ArrayComponentsJoinedByString( fn Factors( n ), @", " ) )nextHandleEventsFactors of 1: [1]Factors of 2: [1, 2]Factors of 3: [1, 3]Factors of 4: [1, 2, 4]Factors of 5: [1, 5]Factors of 6: [1, 2, 3, 6]Factors of 7: [1, 7]Factors of 8: [1, 2, 4, 8]Factors of 9: [1, 3, 9]Factors of 10: [1, 2, 5, 10]Factors of 20: [1, 2, 4, 5, 10, 20]Factors of 40: [1, 2, 4, 5, 8, 10, 20, 40]Factors of 60: [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]Factors of 80: [1, 2, 4, 5, 8, 10, 16, 20, 40, 80]Factors of 100: [1, 2, 4, 5, 10, 20, 25, 50, 100]Factors of 200: [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 200]Factors of 300: [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]Factors of 400: [1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 200, 400]Factors of 512: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]Factors of 677: [1, 677]Factors of 768: [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 768]Factors of 966: [1, 2, 3, 6, 7, 14, 21, 23, 42, 46, 69, 138, 161, 322, 483, 966]Factors of 1000: [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000]Factors of 1024: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]Factors of 2048: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]Factors of 4096: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]
# Built-in functionDivisorsInt(Factorial(5));# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]# A possible implementation, not suitable to large ndiv:=n->Filtered([1..n],k->nmodk=0);div(Factorial(5));# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]# Another implementation, usable for large n (if n can be factored quickly)div2:=function(n)localf,p;f:=Collected(FactorsInt(n));p:=List(f,v->List([0..v[2]],k->v[1]^k));returnSortedList(List(Cartesian(p),Product));end;div2(Factorial(5));# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]
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.
packagemainimport"fmt"funcmain(){printFactors(-1)printFactors(0)printFactors(1)printFactors(2)printFactors(3)printFactors(53)printFactors(45)printFactors(64)printFactors(600851475143)printFactors(999999999999999989)}funcprintFactors(nrint64){ifnr<1{fmt.Println("\nFactors of",nr,"not computed")return}fmt.Printf("\nFactors of %d: ",nr)fs:=make([]int64,1)fs[0]=1apf:=func(pint64,eint){n:=len(fs)fori,pp:=0,p;i<e;i,pp=i+1,pp*p{forj:=0;j<n;j++{fs=append(fs,fs[j]*pp)}}}e:=0for;nr&1==0;e++{nr>>=1}apf(2,e)ford:=int64(3);nr>1;d+=2{ifd*d>nr{d=nr}fore=0;nr%d==0;e++{nr/=d}ife>0{apf(d,e)}}fmt.Println(fs)fmt.Println("Number of factors =",len(fs))}
Factors of -1 not computedFactors of 0 not computedFactors of 1: [1]Number of factors = 1Factors of 2: [1 2]Number of factors = 2Factors of 3: [1 3]Number of factors = 2Factors of 53: [1 53]Number of factors = 2Factors of 45: [1 3 9 5 15 45]Number of factors = 6Factors of 64: [1 2 4 8 16 32 64]Number of factors = 7Factors of 600851475143: [1 71 839 59569 1471 104441 1234169 87625999 6857 486847 5753023 408464633 10086647 716151937 8462696833 600851475143]Number of factors = 16Factors of 999999999999999989: [1 999999999999999989]Number of factors = 2
{.),1>\{\%!}+,}:f;60 f`[1 2 3 4 5 6 10 12 15 20 30 60]
varnumbers={11,21,32,45,67,96}numbers.each(\number->printFactors(number))functionprintFactors(n:int){if(n<1)returnvarresult="${n} => "(1..n/2).each(\i->{result+=n%i==0?"${i} ":""})print("${result}${n}")}
11 => 1 1121 => 1 3 7 2132 => 1 2 4 8 16 3245 => 1 3 5 9 15 4567 => 1 6796 => 1 2 3 4 6 8 12 16 24 32 48 96
A straight brute force approach up to the square root ofN:
deffactorize={longtarget->if(target==1)return[1L]if(target<4)return[1L,target]deftargetSqrt=Math.sqrt(target)deflowfactors=(2L..targetSqrt).grep{(target%it)==0}if(lowfactors==[])return[1L,target]defnhalf=lowfactors.size()-((lowfactors[-1]==targetSqrt)?1:0)[1]+lowfactors+(0..<nhalf).collect{target.intdiv(lowfactors[it])}.reverse()+[target]}
Test:
((1..30)+[333333]).each{println([number:it,factors:factorize(it)])}
[number:1, factors:[1]][number:2, factors:[1, 2]][number:3, factors:[1, 3]][number:4, factors:[1, 2, 4]][number:5, factors:[1, 5]][number:6, factors:[1, 2, 3, 6]][number:7, factors:[1, 7]][number:8, factors:[1, 2, 4, 8]][number:9, factors:[1, 3, 9]][number:10, factors:[1, 2, 5, 10]][number:11, factors:[1, 11]][number:12, factors:[1, 2, 3, 4, 6, 12]][number:13, factors:[1, 13]][number:14, factors:[1, 2, 7, 14]][number:15, factors:[1, 3, 5, 15]][number:16, factors:[1, 2, 4, 8, 16]][number:17, factors:[1, 17]][number:18, factors:[1, 2, 3, 6, 9, 18]][number:19, factors:[1, 19]][number:20, factors:[1, 2, 4, 5, 10, 20]][number:21, factors:[1, 3, 7, 21]][number:22, factors:[1, 2, 11, 22]][number:23, factors:[1, 23]][number:24, factors:[1, 2, 3, 4, 6, 8, 12, 24]][number:25, factors:[1, 5, 25]][number:26, factors:[1, 2, 13, 26]][number:27, factors:[1, 3, 9, 27]][number:28, factors:[1, 2, 4, 7, 14, 28]][number:29, factors:[1, 29]][number:30, factors:[1, 2, 3, 5, 6, 10, 15, 30]][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]]
UsingD. Amos'es Primes module for finding prime factors
importHFM.Primes(primePowerFactors)importControl.Monad(mapM)importData.List(product)-- primePowerFactors :: Integer -> [(Integer,Int)]factors=mapproduct.mapM(\(p,m)->[p^i|i<-[0..m]]).primePowerFactors
Returns list of factors out of order, e.g.:
~>factors42[1,7,3,21,2,14,6,42]
Or,prime decomposition task can be used (although, a trial division-only version will become very slow for large primes),
importData.List(group)primePowerFactors=map(\x->(headx,lengthx)).group.factorize
The above function can also be found in the packagearithmoi, asMath.NumberTheory.Primes.factorise :: Integer -> [(Integer, Int)],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:
integerFactors::Int->[Int]integerFactorsn|1>n=[]|otherwise=lows<>(quotn<$>partn(reverselows))wherepartn|n==square=tail|otherwise=id(square,lows)=(,).(^2)<*>(filter((0==).remn).enumFromTo1)$floor(sqrt$fromIntegraln)main::IO()main=print$integerFactors600
[1,2,3,4,5,6,8,10,12,15,20,24,25,30,40,50,60,75,100,120,150,200,300,600]
Naive, functional, no import, in increasing order:
factorsNaiven=[i|i<-[1..n],modni==0]
~>factorsNaive25[1,5,25]
Factor,cofactor. Get the list of factor–cofactor pairs sorted, for a quadratic speedup:
importData.List(sort)factorsCon=sort[i|i<-[1..floor(sqrt(fromIntegraln))],(d,0)<-[divModni],i<-i:[d|d>i]]
A version of the above without the need for sorting, making it to beonline (i.e. productive immediately, which can be seen in GHCi); factors in increasing order:
factorsOn=ds++[r|(d,0)<-[divModnr],r<-r:[d|d>r]]++reverse(map(n`div`)ds)wherer=floor(sqrt(fromIntegraln))ds=[i|i<-[1..r-1],modni==0]
Testing:
*Main>:set+s~>factorsO120[1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120](0.00secs,0bytes)~>factorsO12041111117[1,7,41,287,541,3787,22181,77551,155267,542857,3179591,22257137,41955091,293685637,1720158731,12041111117](0.09secs,50758224bytes)
DLG(NameEdit=N, TItle='Enter an integer') DO i = 1, N^0.5 IF( MOD(N,i) == 0) WRITE() i, N/i ENDDOEND
proceduremain(arglist)numbers:=arglist|||[32767,45,53,64,100]# combine command line provided and default set of valueseverywrites(lf,"factors of ",i:=!numbers,"=")&writes(divisors(i)," ")dolf:="\n"endlinkfactors
factors of 32767=1 7 31 151 217 1057 4681 32767factors of 45=1 3 5 9 15 45factors of 53=1 53factors of 64=1 2 4 8 16 32 64factors of 100=1 2 4 5 10 20 25 50 100
(function factors n (filter (div? n) (range 1 (inc n))))(factors 45)
[1 3 5 9 15 45]
The "brute force" approach is the most concise:
foi=:[:I.0=(|~i.@>:)
Example use:
foi4012458102040
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.
q:402225
Alternatively, q: can produce provide a table of the exponents of the unique relevant prime factors
__q:42023572111
With this, we can form lists of each of the potential relevant powers of each of these prime factors
(^i.@>:)&.>/__q:420┌─────┬───┬───┬───┐│124│13│15│17│└─────┴───┴───┴───┘
From here, it's a simple matter (*/&>@{ or, find all possible combinations of one item from each list ({ without a left argument) then unpack each list and multiply its elements) to compute all possible factors of the original number
factrs=:*/&>@{@((^i.@>:)&.>/)@q:~&__factrs4015210420840
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:
factrst=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__ factrst 4201 2 3 4 5 6 7 10 12 14 15 20 21 28 30 35 42 60 70 84 105 140 210 420A less efficient, but concise variation on this theme:
~.,*/&> { 1 ,&.> q: 401 5 2 10 4 20 8 40This 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:
factors 5684742201 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
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:
factors 568474220x1 2 4 5 10 17 20 34 68 85 170 340 1671983 3343966 6687932 8359915 16719830 28423711 33439660 56847422 113694844 142118555 284237110 568474220
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:
factorsOfNumber=: monad define Y=. y"_ /:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y) factorsOfNumber 401 2 4 5 8 10 20 40
Another approach:
odometer =: #: i.@(*/)factors=: (*/@:^"1 odometer@:>:)/@q:~&__
See also the J essaysOdometer andDivisors.
public static TreeSet<Long> factors(long n){ TreeSet<Long> factors = new TreeSet<Long>(); factors.add(n); factors.add(1L); for(long test = n - 1; test >= Math.sqrt(n); test--) if(n % test == 0) { factors.add(test); factors.add(n / test); } return factors;}function factors(num){ var n_factors = [], i; for (i = 1; i <= Math.floor(Math.sqrt(num)); i += 1) if (num % i === 0) { n_factors.push(i); if (num / i !== i) n_factors.push(num / i); } n_factors.sort(function(a, b){return a - b;}); // numeric sort return n_factors;}factors(45); // [1,3,5,9,15,45] factors(53); // [1,53] factors(64); // [1,2,4,8,16,32,64]Translating the naive list comprehension example from Haskell, using a list monad for the comprehension
// Monadic bind (chain) for listsfunction 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)Output:
[1, 2, 3, 6]
Translating the Haskell (lows and highs) example
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]));Output:
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
(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]);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
# This implementation uses "sort" for tidinessdef factors: . as $num | reduce range(1; 1 + sqrt|floor) as $i ([]; if ($num % $i) == 0 then ($num / $i) as $r | if $i == $r then . + [$i] else . + [$i, $r] end else . end ) | sort; def task: (45, 53, 64) | "\(.): \(factors)" ;task
$ jq -n -M -r -c -f factors.jq45: [1,3,5,9,15,45]53: [1,53]64: [1,2,4,8,16,32,64]
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))...))))endconst examples = [28, 45, 53, 64, 6435789435768]for n in examples @time println("The factors of $n are: $(factors(n))")endThe 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)
f:{i:{y[&x=y*x div y]}[x;1+!_sqrt x];?i,x div|i}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 1201 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120 f 10241 2 4 8 16 32 64 128 256 512 1024 f 6008514751431 71 839 1471 6857 59569 104441 486847 1234169 5753023 10086647 87625999 408464633 716151937 8462696833 600851475143 #f 3491888400 / has 1920 factors1920 / Number of factors for 3491888400 .. 3491888409 #:'f' 3491888400+!101920 16 4 4 12 16 32 16 8 24fun 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)}11 => 1 1121 => 1 3 7 2132 => 1 2 4 8 16 3245 => 1 3 5 9 15 4567 => 1 6796 => 1 2 3 4 6 8 12 16 24 32 48 96
{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 64This 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))
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." (factors n 2 '()))(defun factors ((1 _ acc) (++ acc '(1))) ((n _ acc) (when (=< n 0)) #(error undefined)) ((n k acc) (when (== 0 (rem n k))) (factors (div n k) k (cons k acc))) ((n k acc) (factors n (+ k 1) acc)))
> (factors 10677106534462215678539721403561279)(104729 104729 104729 98731 98731 32579 29269 1)
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 resend
put factors(45)-- [1, 3, 5, 9, 15, 45]put factors(53)-- [1, 53]put factors(64)-- [1, 2, 4, 8, 16, 32, 64]
to factors :n output filter [equal? 0 modulo :n ?] iseq 1 :nendshow factors 28 ; [1 2 4 7 14 28]
function Factors( n ) local f = {} for i = 1, n/2 do if n % i == 0 then f[#f+1] = i end end f[#f+1] = n return fend\\ Factors of an integer\\ For act as BASIC's FOR (if N<1 no loop start)FORM 60,40SET 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 LikeBasicSET 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 LikeM2000numtheory:-divisors(n);
Factorize[n_Integer] := Divisors[n]
function fact(n); f = factor(n);% prime decomposition K = dec2bin(0:2^length(f)-1)-'0'; % generate all possible permutations F = ones(1,2^length(f)); for k = 1:size(K) F(k) = prod(f(~K(k,:)));% and compute products end; F = unique(F);% eliminate duplicates printf('There are %i factors for %i.\n',length(F),n); disp(F); end;>> fact(12)There are 6 factors for 12. 1 2 3 4 6 12>> fact(28)There are 6 factors for 28. 1 2 4 7 14 28>> fact(64)There are 7 factors for 64. 1 2 4 8 16 32 64>>fact(53)There are 2 factors for 53. 1 53
The builtindivisors function does this.
(%i96) divisors(100);(%o96) {1,2,4,5,10,20,25,50,100}Such a function could be implemented like so:
divisors2(n) := map( lambda([l], lreduce("*", l)), apply( cartesian_product, map( lambda([fac], setify(makelist(fac[1]^i, i, 0, fac[2]))), ifactors(n))));fn factors n =(return (for i = 1 to n+1 where mod n i == 0 collect i))
factors 3#(1, 3)factors 7#(1, 7)factors 14#(1, 2, 7, 14)factors 60#(1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60)factors 54#(1, 2, 3, 6, 9, 18, 27, 54)
Mercury is both a logic language and a functional language. As such there are two possible interfaces for calculating the factors of an integer. This code shows both styles of implementation. Note that much of the code here is ceremony put in place to have this be something which can actually compile. The actual factoring is contained in the predicatefactor/2 and in the functionfactor/1. The function form is implemented in terms of the predicate form rather than duplicating all of the predicate code.
The predicates main/2 and factor/2 are shown with the combined type and mode statement (e.g. int::in) as is the usual case for simple predicates with only one mode. This makes the code more immediately understandable. The predicate factor/5, however, has its mode broken out onto a separate line both to show Mercury's mode statement (useful for predicates which can have varying instantiation of parameters) and to stop the code from extending too far to the right. Finally the function factor/1 has its mode statements removed (shown underneath in a comment for illustration purposes) because good coding style (and the default of the compiler!) has all parameters "in"-moded and the return value "out"-moded.
This implementation of factoring works as follows:
This implementation makes use of Mercury's "state variable notation" to keep a pair of variables for accumulation, thus allowing the implementation to be tail recursive. !Accumulator is syntax sugar for a *pair* of variables. One of them is an "in"-moded variable and the other is an "out"-moded variable. !:Accumulator is the "out" portion and !.Accumulator is the "in" portion in the ensuing code.
Using the state variable notation avoids having to keep track of strings of variables unified in the code named things like Acc0, Acc1, Acc2, Acc3, etc.
:- module fac.:- interface.:- import_module io.:- pred main(io::di, io::uo) is det.:- implementation.:- import_module float, int, list, math, string.main(!IO) :- io.command_line_arguments(Args, !IO), list.filter_map(string.to_int, Args, CleanArgs), list.foldl((pred(Arg::in, !.IO::di, !:IO::uo) is det :- factor(Arg, X), io.format("factor(%d, [", [i(Arg)], !IO), io.write_list(X, ",", io.write_int, !IO), io.write_string("])\n", !IO) ), CleanArgs, !IO).:- pred factor(int::in, list(int)::out) is det.factor(N, Factors) :- Limit = float.truncate_to_int(math.sqrt(float(N))),factor(N, 2, Limit, [], Unsorted), list.sort_and_remove_dups([1, N | Unsorted], Factors). :- pred factor(int, int, int, list(int), list(int)).:- mode factor(in, in, in, in, out) is det.factor(N, X, Limit, !Accumulator) :- ( if X > Limit then true else ( if 0 = N mod X then !:Accumulator = [X, N / X | !.Accumulator] else true ), factor(N, X + 1, Limit, !Accumulator) ).:- func factor(int) = list(int).%:- mode factor(in) = out is det.factor(N) = Factors :- factor(N, Factors).:- end_module fac.Use of the code looks like this:
$ mmc fac.m && ./fac 100 999 12345678 boogerfactor(100, [1,2,4,5,10,20,25,50,100])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])
(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) :factors24 factors puts!9 factors puts!11 factors puts!
factors = function(n) result = [1] for i in range(2, n) if n % i == 0 then result.push i end for return resultend functionwhile true n = val(input("Number to factor (0 to quit)? ")) if n <= 0 then break print factors(n)end whileNumber 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
П91П6КИП6ИП9ИП6/П8^[x]x#021-x=003ИП6С/ПИП8П9БП041С/ПБП21
factors(num)New fctr,list,sep,sqrtIf num<1 Quit "Too small a number"If num["." Quit "Not an integer"Set sqrt=num**0.5\1For fctr=1:1:sqrt Set:num/fctr'["." list(fctr)=1,list(num/fctr)=1Set (list,fctr)="",sep="[" For Set fctr=$Order(list(fctr)) Quit:fctr="" Set list=list_sep_fctr,sep=","Quit list_"]"w $$factors(45) ; [1,3,5,9,15,45]w $$factors(53) ; [1,53]w $$factors(64) ; [1,2,4,8,16,32,64]
n = int(input())for i in range(1, n / 2) if (n % i = 0)print i + " "endendprintln n
/* NetRexx ************************************************************ 21.04.2013 Walter Pachl* 21.04.2013 add method main to accept argument(s)*********************************************************************/options replace format comments java crossref symbols nobinaryclass divl method main(argwords=String[]) static arg=Rexx(argwords) Parse arg a b Say a b If a='' Then Do help='java divl low [high] shows' help=help||' divisors of all numbers between low and high' Say help Return End If b='' Then b=a loop x=a To b say x '->' divs(x) Endmethod divs(x) public static returns Rexx if x==1 then return 1 /*handle special case of 1 */ lo=1 hi=x odd=x//2 /* 1 if x is odd */ loop j=2+odd By 1+odd While j*j<x /*divide by numbers<sqrt(x) */ if x//j==0 then Do /*Divisible? Add two divisors:*/ lo=lo j /* list low divisors */ hi=x%j hi /* list high divisors */ End End If j*j=x Then /*for a square number as input */ lo=lo j /* add its square root */ return lo hi /* return both lists */
java divl 1 101 -> 12 -> 1 23 -> 1 34 -> 1 2 45 -> 1 56 -> 1 2 3 67 -> 1 78 -> 1 2 4 89 -> 1 3 910 -> 1 2 5 10
import intsets, math, algorithm proc factors(n: int): seq[int] = var fs: IntSet 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) result.sort() echo factors(45)
[ 'n ; [ negative-or-zero [ , ] if [ n not-factor [ , ] when ] else ] n times n ] 'factors ;[ dup 0 <= ] 'negative-or-zero ;[ swap dup rot swap mod 0 = not ] 'not-factor ;( tests )100 factors .s .clr ( => 1 2 4 5 10 20 25 50 100 ) newline53 factors .s .clr ( => 1 53 ) newline64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline12 factors .s .clr ( => 1 2 3 4 6 12 )
Oxford Oberon-2
MODULE Factors;IMPORT Out,SYSTEM;TYPELIPool = POINTER TO ARRAY OF LONGINT;LIVector= POINTER TO LIVectorDesc;LIVectorDesc = RECORDcap: INTEGER;len: INTEGER;LIPool: LIPool;END;PROCEDURE New(cap: INTEGER): LIVector;VARv: LIVector;BEGINNEW(v);v.cap := cap;v.len := 0;NEW(v.LIPool,cap);RETURN vEND New;PROCEDURE (v: LIVector) Add(x: LONGINT);VAR newLIPool: LIPool;BEGINIF v.len = LEN(v.LIPool^) THEN(* run out of space *)v.cap := v.cap + (v.cap DIV 2);NEW(newLIPool,v.cap);SYSTEM.MOVE(SYSTEM.ADR(v.LIPool^),SYSTEM.ADR(newLIPool^),v.cap * SIZE(LONGINT));v.LIPool := newLIPoolEND;v.LIPool[v.len] := x;INC(v.len)END Add;PROCEDURE (v: LIVector) At(idx: INTEGER): LONGINT;BEGINRETURN v.LIPool[idx];END At;PROCEDURE Factors(n:LONGINT): LIVector;VAR j: LONGINT;v: LIVector;BEGINv := New(16);FOR j := 1 TO n DOIF (n MOD j) = 0 THEN v.Add(j) END;END; RETURN vEND Factors;VARv: LIVector;j: INTEGER;BEGINv := Factors(123);FOR j := 0 TO v.len - 1 DOOut.LongInt(v.At(j),4);Out.LnEND;Out.Int(v.len,6);Out.String(" factors");Out.LnEND Factors.1 3 41 123 4 factors
use IO;use Structure;bundle Default { class Basic { function : native : GenerateFactors(n : Int) ~ IntVector { factors := IntVector->New(); factors-> AddBack(1); factors->AddBack(n); for(i := 2; i * i <= n; i += 1;) { if(n % i = 0) { factors->AddBack(i); if(i * i <> n) { factors->AddBack(n / i); }; }; }; factors->Sort(); return factors; } function : Main(args : String[]) ~ Nil { numbers := [3135, 45, 60, 81]; for(i := 0; i < numbers->Size(); i += 1;) { factors := GenerateFactors(numbers[i]); Console->GetInstance()->Print("Factors of ")->Print(numbers[i])->PrintLine(" are:"); each(i : factors) { Console->GetInstance()->Print(factors->Get(i))->Print(", "); }; "\n\n"->Print(); }; } }}let rec range = function 0 -> [] | n -> range(n-1) @ [n]let factors n = List.filter (fun v -> (n mod v) = 0) (range n)
Uses built-in dynamic arrays, and only checks up to the square root
package mainimport "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) }}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]
Integer method: factors self seq filter(#[ self isMultiple ]) ;120 factors println
[1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]
declare fun {Factors N} Sqr = {Float.toInt {Sqrt {Int.toFloat N}}} Fs = for X in 1..Sqr append:App do if N mod X == 0 then CoFactor = N div X in if CoFactor == X then %% avoid duplicate factor {App [X]} %% when N is a square number else {App [X CoFactor]} end end end in {Sort Fs Value.'<'} endin {Show {Factors 53}}Panda has a factor function already, it's defined as:
fun factor(n) type integer->integer f where n.mod(1..n=>f)==045.factor
divisors(n)
program Factors;var i, number: integer;begin write('Enter a number between 1 and 2147483647: '); readln(number); for i := 1 to round(sqrt(number)) - 1 do if number mod i = 0 then write (i, ' ', number div i, ' '); // Check to see if number is a square i := round(sqrt(number)); if i*i = number then write(i) else if number mod i = 0 then write(i, number/i); writeln;end.Enter a number between 1 and 2147483647: 491 49 7Enter a number between 1 and 2147483647: 3534351 25755 3 8585 5 5151 15 1717 17 1515 51 505 85 303 101 255
like [C Prime_factoring].
Insertion sort was much faster, because mostly not so many factors need to be sorted.
"runtime overhead" +25% instead +100% for quicksort against no sort.
Especially fast for consecutive integers.
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 decompositionconst//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 cachetype 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 numbersconst 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 0var 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,j,k,pr,fac,n,MaxP : Uint64;begin n := pdfOfs; if n+SizePrDeFe >= sqr(SmallPrimes[High(SmallPrimes)]) then EXIT(FALSE); //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 with pdf[i] do begin j := BsfQWord(n+i); pfMaxIdx := 1; pfpotPrimIdx[0] := 0; 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 BREAK; //j is power of prime j := CnvtoBASE(dgt,n+k,pr); 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 Globalbegin 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.TIO.RUN//out-commented GetDivisors, but still calculates sum of divisors and count of divisorsruntime 0.555 s1,11,9090911,11,909091,10000001simple versionruntime 8.167 s1,11,9090911,11,909091,10000001Real time: 8.868 s CPU share: 99.57 %//with GetDivisorsruntime 1.815 s1,11,9090911,11,909091,10000001simple versionruntime 11.057 s1,11,9090911,11,909091,10000001Real time: 13.082 s CPU share: 99.16 %
function Factors(n: integer): List<integer>;begin var res := HSet(1,n); for var i:=2 to n.Sqrt.Trunc do if n.Divs(i) then begin res.Add(i); res.Add(n div i); end; Result := res.Order.ToList;end;begin foreach var x in |45,53,64| do Println(x,Factors(x));end.
45 [1,3,5,9,15,45]53 [1,53]64 [1,2,4,8,16,32,64]
sub factors{ my($n) = @_; return grep { $n % $_ == 0 }(1 .. $n);}print join ' ',factors(64), "\n";Or more intelligently:
sub factors { my $n = shift; $n = -$n if $n < 0; my @divisors; for (1 .. int(sqrt($n))) { # faster and less memory than map/grep push @divisors, $_ unless $n % $_; } # Return divisors including top half, without duplicating a square @divisors, map { $_*$_ == $n ? () : int($n/$_) } reverse @divisors;}print join " ", factors(64), "\n";One could also use a module, e.g.:
use ntheory qw/divisors/;print join " ", divisors(12345678), "\n";# Alternately something like: fordivisors { say } 12345678;There is a builtin factors(n), which takes an optional second parameter to include 1 and n:
?factors(12345,1)
{1,3,5,15,823,2469,4115,12345}You can find the implementation of factors(), prime_factors(), and prime_powers() in builtins\pfactors.e,
and mpz_factors(), mpz_prime_factors(), and mpz_pollard_rho() in mpfr.e for larger numbers, for example:
requires("1.0.2")-- [p2js/integer() bugs]includempfr.e?shorten(factors(3491888400),"factors",4)-- {2,3,4,5,"...",698377680,872972100,1163962800.0,1745944200.0," (1,918 factors)"}?shorten(mpz_factors(3491888400),"factors",4)-- {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?prime_factors(3491888400)-- {2,3,5,7,11,13,17,19}?prime_powers(3491888400)-- {{2,4},{3,3},{5,2},{7,1},{11,1},{13,1},{17,1},{19,1}}?vslice(mpz_prime_factors("3491888400",10000),1)-- {2,3,5,7,11,13,17,19}?mpz_prime_factors("3491888400",10000)-- {{2,4},{3,3},{5,2},{7,1},{11,1},{13,1},{17,1},{19,1}}-- Note that mpz_prime_factors() only accepts string or mpz, and not a raw native atom/integer.?length(factors(108233175859200,1))-- 666?length(mpz_factors(108233175859200,1))-- 666stringd="10677106534462215678539721403561279"?mpz_prime_factors(d,10000)-- {{29269,1},{32579,1},{98731,2},{104729,3}}?shorten(mpz_factors(d,1),"factors",2)-- {1,29269,"...","364792324112959639158827476291","10677106534462215678539721403561279"," (48 factors)"}
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?
/# Rosetta Code problem: http://rosettacode.org/wiki/Factors_of_an_integerby Galileo, 05/2022 #/include ..\Utilitys.pmtdef Factors >ps ( ( 1 tps 2 / ) for tps over mod if drop endif endfor ps> )enddef11 Factors21 Factors32 factors45 factors67 factors96 factorspstack
[[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 ===
function GetFactors($n){ $factors = array(1, $n); for($i = 2; $i * $i <= $n; $i++){ if($n % $i == 0){ $factors[] = $i; if($i * $i != $n) $factors[] = $n/$i; } } sort($factors); return $factors;}factors(N) = [[D,N // D] : D in 1..N.sqrt.floor, N mod D == 0].flatten.sort_remove_dups.
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 ).
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.
Let's compare with 18! (6402373705728000) which has 14688 factors. The recursive version is slightly faster than the loop + set version.
go => N = 6402373705728000, % factorial(18), println("factors:"), time(_Fs1 = factors(N)) , println("factors2:"), time(factors2(N,_Fs2)), println("factors3:"), time(Fs3=factors3(N)).len),factors:CPU time 3.938 seconds.factors2:CPU time 3.108 seconds.factors3:CPU time 3.159 seconds.
(de factors (N) (filter '((D) (=0 (% N D))) (range 1 N) ) )
T :Enter a number.A :#nC :factor = 1T :The factors of #n are:*LoopC :remainder = n % factorT ( remainder = 0 ) :#factorJ ( factor = n ) :*FinishedC :factor = factor + 1J :*Loop*FinishedEND:
PL/0 does not handle strings. So, no prompt. The program waits for entering a number, and then displays the factors.
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.
4 runs.
1
1
11
1 2 3 4 6 12
13
1 13
-22222
1 2 41 82 271 542 11111 22222
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;
factors of: 90 : 1 2 3 5 6 9 10 15 18 30 45 90factors of: 91 : 1 7 13 91factors of: 92 : 1 2 4 23 46 92factors of: 93 : 1 3 31 93factors of: 94 : 1 2 47 94factors of: 95 : 1 5 19 95factors of: 96 : 1 2 3 4 6 8 12 16 24 32 48 96factors of: 97 : 1 97factors of: 98 : 1 2 7 14 49 98factors of: 99 : 1 3 9 11 33 99factors of: 100 : 1 2 4 5 10 20 25 50 100
See also#Polyglot:PL/I and PL/M
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.
The factors of 11:1 11The factors of 21:1 21 3 7The factors of 519:1 519 3 173
... under CP/M (or an emulator)
Should work with many PL/I implementations.
The PL/I include file "pg.inc" can be found on thePolyglot: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.
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;
FACTORS OF: 90: 1 2 3 5 6 9 10 15 18 30 45 90FACTORS OF: 91: 1 7 13 91FACTORS OF: 92: 1 2 4 23 46 92FACTORS OF: 93: 1 3 31 93FACTORS OF: 94: 1 2 47 94FACTORS OF: 95: 1 5 19 95FACTORS OF: 96: 1 2 3 4 6 8 12 16 24 32 48 96FACTORS OF: 97: 1 97FACTORS OF: 98: 1 2 7 14 49 98FACTORS OF: 99: 1 3 9 11 33 99FACTORS OF: 100: 1 2 4 5 10 20 25 50 100
function Get-Factor ($a) { 1..$a | Where-Object { $a % $_ -eq 0 }}This one uses a range of integers up to the target number and just filters it using theWhere-Object cmdlet. It's very slow though, so it is not very usable for larger numbers.
function Get-Factor ($a) { 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.
Uses the math module:
editvar /newvar /value=a /userinput=1 /title=Enter an integer:do /delimspaces %% -a- >bprintline Factors of -a-: -b-
Simple Brute Force Implementation
brute_force_factors( N , Fs ) :- integer(N) , N > 0 , setof( F , ( between(1,N,F) , N mod F =:= 0 ) , Fs ) .
A Slightly Smarter Implementation
smart_factors(N,Fs) :- integer(N) , N > 0 , setof( F , factor(N,F) , Fs ) .factor(N,F) :- L is floor(sqrt(N)) , between(1,L,X) , 0 =:= N mod X , ( F = X ; F is N // X ) .
Not every Prolog hasbetween/3: you might need this:
between(X,Y,Z) :- integer(X) , integer(Y) , X =< Z , between1(X,Y,Z) .between1(X,Y,X) :- X =< Y .between1(X,Y,Z) :- X < Y , X1 is X+1 , between1(X1,Y,Z) .
?- N=36 ,( brute_force_factors(N,Factors) ; smart_factors(N,Factors) ).N = 36, Factors = [1, 2, 3, 4, 6, 9, 12, 18, 36] ;N = 36, Factors = [1, 2, 3, 4, 6, 9, 12, 18, 36] .?- N=53,( brute_force_factors(N,Factors) ; smart_factors(N,Factors) ).N = 53, Factors = [1, 53] ;N = 53, Factors = [1, 53] .?- N=100,( brute_force_factors(N,Factors);smart_factors(N,Factors) ).N = 100, Factors = [1, 2, 4, 5, 10, 20, 25, 50, 100] ;N = 100, Factors = [1, 2, 4, 5, 10, 20, 25, 50, 100] .?- N=144,( brute_force_factors(N,Factors);smart_factors(N,Factors) ).N = 144, Factors = [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144] ;N = 144, Factors = [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144] .?- N=32765,( brute_force_factors(N,Factors);smart_factors(N,Factors) ).N = 32765, Factors = [1, 5, 6553, 32765] ;N = 32765, Factors = [1, 5, 6553, 32765] .?- N=32766,( brute_force_factors(N,Factors);smart_factors(N,Factors) ).N = 32766, Factors = [1, 2, 3, 6, 43, 86, 127, 129, 254, 258, 381, 762, 5461, 10922, 16383, 32766] ;N = 32766, Factors = [1, 2, 3, 6, 43, 86, 127, 129, 254, 258, 381, 762, 5461, 10922, 16383, 32766] .38 ?- N=32767,( brute_force_factors(N,Factors);smart_factors(N,Factors) ).N = 32767, Factors = [1, 7, 31, 151, 217, 1057, 4681, 32767] ;N = 32767, Factors = [1, 7, 31, 151, 217, 1057, 4681, 32767] .
Naive and slow but simplest (check all numbers from 1 to n):
>>> def factors(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):
>>> def factors(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)):
from math import isqrtdef factor(n): factors1, factors2 = [], [] for x in range(1, isqrt(n)): if n % x == 0: factors1.append(x) factors2.append(n // x) x += 1 if x * x == n: factors1.append(x) factors1.extend(reversed(factors2)) return factors1for i in 45, 53, 64: print("%i: factors: %s" % (i, factor(i)))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:
from itertools import chain, cycle, accumulate # last of which is Python 3 onlydef factors(n): def prime_powers(n): # c goes through 2, 3, 5, then the infinite (6n+1, 6n+5) series for c in accumulate(chain([2, 1, 2], cycle([2,4]))): if c*c > n: break if n%c: continue d,p = (), c while not n%c: n,p,d = n//c, p*c, d + (p,) yield(d) if n > 1: yield((n,)) r = [1] for e in prime_powers(n): r += [a*b for a in r for b in e] return r
sqrt+ is defined atIsqrt (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 thedrop 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.
[ [] 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 ]
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, 910: 1, 2, 5, 1011: 1, 1112: 1, 2, 3, 4, 6, 1213: 1, 1314: 1, 2, 7, 1415: 1, 3, 5, 1516: 1, 2, 4, 8, 1617: 1, 1718: 1, 2, 3, 6, 9, 1819: 1, 1920: 1, 2, 4, 5, 10, 20
factors <- function(n){ if(length(n) > 1) { lapply(as.list(n), factors) } else { one.to.n <- seq_len(n) one.to.n[(n %% one.to.n) == 0] }}>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[[2]][1] 1 53[[3]][1] 1 2 4 8 16 32 64
With identical output, a more idiomatic way is to use R's Filter.
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)
#lang racket;; a naive version(define (naive-factors n) (for/list ([i (in-range 1 (add1 n))] #:when (zero? (modulo n i))) i))(naive-factors 120) ; -> '(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120);; much better: use `factorize' to get prime factors and construct the;; list of results from that(require math)(define (factors n) (sort (for/fold ([l '(1)]) ([p (factorize n)]) (append (for*/list ([e (in-range 1 (add1 (cadr p)))] [x l]) (* x (expt (car p) e))) l)) <))(naive-factors 120) ; -> same;; to see how fast it is:(define huge 1200034005600070000008900000000000000000)(time (length (factors huge)));; I get 42ms for getting a list of 7776 numbers;; but actually the math library comes with a `divisors' function that;; does the same, except even faster(divisors 120) ; -> same(time (length (divisors huge)));; And this one clocks at 17ms
(formerly Perl 6)
Naive, brute-force, and slow, but ok for small numbers.
sub factors (Int $n) { (1..$n).grep($n %% *) }If you don't want to roll your own.
use Prime::Factor;put divisors :s, 2⁹⁹ + 1;say (now - INIT now).round(.001) ~' seconds';
1 3 9 19 27 57 67 171 201 513 603 683 1273 1809 2049 3819 5347 6147 11457 12977 16041 18441 20857 34371 38931 45761 48123 62571 101593 116793 137283 144369 187713 304779 350379 358249 396283 411849 563139 869459 914337 1074747 1188849 1235547 1397419 2608377 2743011 3224241 3566547 3652001 4192257 6806731 7825131 9672723 10699641 10956003 12576771 14245331 20420193 23475393 26550961 32868009 37730313 42735993 61260579 69388019 79652883 98604027 111522379 128207979 183781737 208164057 238958649 244684067 270661289 334567137 384623937 624492171 716875947 734052201 811983867 954437177 1003701411 1873476513 2118925201 2202156603 2435951601 2863311531 3011104233 4648997273 6356775603 6606469809 7307854803 7471999393 8589934593 13946991819 18134306363 19070326809 22415998179 25769803779 41840975457 54402919089 57210980427 67247994537 76169784857 125522926371 141967988467 163208757267 201743983611 228509354571 425903965401 489626271801 685528063713 1277711896203 1447225912283 2056584191139 3833135688609 4341677736849 5103375585419 13025033210547 15310126756257 39075099631641 45930380268771 96964136122961 137791140806313 242099935645987 290892408368883 726299806937961 872677225106649 2178899420813883 2618031675319947 4599898777273753 6536698262441649 13799696331821259 16220695688281129 41399088995463777 48662087064843387 124197266986391331 145986261194530161 165354256046209121 308193218077341451 437958783583590483 496062768138627363 924579654232024353 1294508355899092489 1488188304415882089 2773738962696073059 3141730864877973299 3883525067697277467 4464564913247646267 5049478357768350859 8321216888088219177 9425192594633919897 11078735155096011107 11650575203091832401 15148435073305052577 24595658762082757291 28275577783901759691 33236205465288033321 34951725609275497203 45445305219915157731 73786976286248271873 84826733351705279073 86732059845239196763 95940088797598666321 99708616395864099963 136335915659745473193 210495967946824211033 221360928858744815619 260196179535717590289 287820266392795998963 299125849187592299889 338315049970479507553 631487903840472633099 664082786576234446857 780588538607152770867 863460799178387996889 884149207079080169987 1014945149911438522659 1647909137059544738497 1894463711521417899297 2341765615821458312601 2590382397535163990667 2652447621237240509961 3044835449734315567977 3448793718355783636697 4943727411178634215491 5683391134564253697891 6427985949439110643507 7957342863711721529883 9134506349202946703931 10346381155067350910091 14831182233535902646473 16798834934502523229753 19283957848317331930521 23872028591135164589649 26999560778987372043073 31039143465202052730273 44493546700607707939419 50396504803507569689259 57851873544951995791563 59237996874298371389129 65527080648759889097243 80998682336962116129219 93117430395606158190819 151189514410522709067777 173555620634855987374689 177713990622895114167387 196581241946279667291729 231069179129837503658699 242996047010886348387657 453568543231568127203331 512991654800760068818387 533141971868685342502161 589743725838839001875187 693207537389512510976097 728988141032659045162971 1125521940611669056393451 1538974964402280206455161 1599425915606056027506483 1769231177516517005625561 1808970572192153926885891 2079622612168537532928291 3376565821835007169180353 4390314403466912569515281 4616924893206840619365483 5426911716576461780657673 6238867836505612598784873 10129697465505021507541059 13170943210400737708545843 13850774679620521858096449 16280735149729385341973019 18440700012048375105418859 30389092396515064522623177 34370440871650924610831929 39512829631202213125637529 48842205449188156025919057 55322100036145125316256577 103111322614952773832495787 118538488893606639376912587 165966300108435375948769731 309333967844858321497487361 350373300228919127002958321 497898900325306127846309193 928001903534574964492462083 1051119900686757381008874963 1235526900807241132063063553 3153359702060272143026624889 3706580702421723396189190659 9460079106180816429079874667 11119742107265170188567571977 23475011115337581509198207507 33359226321795510565702715931 70425033346012744527594622521 211275100038038233582783867563 6338253001141147007483516026890.046 seconds
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]
$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>)>; };};1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
program factors(num)relation factinsert 1set i = 2while i < num / 2if num / i = floor(num/i)insert iend ifset i = i + 1end whileinsert numprintend program
/* REXX **************************************************************** Program to calculate and show divisors of positive integer(s).* 03.08.2012 Walter Pachl simplified the above somewhat* in particular I see no benefit from divAdd procedure* 04.08.2012 the reference to 'above' is no longer valid since that* was meanwhile changed for the better.* 04.08.2012 took over some improvements from new above**********************************************************************/Parse arg low high .Select When low='' Then Parse Value '1 200' with low high When high='' Then high=low Otherwise Nop Enddo j=low to high say ' n = ' right(j,6) " divisors = " divs(j) endexitdivs: procedure; parse arg x if x==1 then return 1 /*handle special case of 1 */ Parse Value '1' x With lo hi /*initialize lists: lo=1 hi=x */ odd=x//2 /* 1 if x is odd */ Do j=2+odd By 1+odd While j*j<x /*divide by numbers<sqrt(x) */ if x//j==0 then Do /*Divisible? Add two divisors:*/ lo=lo j /* list low divisors */ hi=x%j hi /* list high divisors */ End End If j*j=x Then /*for a square number as input */ lo=lo j /* add its square root */ return lo hi /* return both lists */
(Shown at 3/4 size.)
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
Modules:How to use
Modules:Source code
The procedure Divisors() is present in Sequences.
-- 22 Mar 2025include Settingssay 'FACTORS OF AN INTEGER'say versionsaynumeric digits 16parse arg l','hif l = '' then l = 1if h = '' then h = 100do i = l to h f = Divisors(i) call Charout ,Right(i,3) 'has' Right(f,2) 'divisors: ' do j = 1 to f call Charout ,divi.j' ' end sayendsay Format(Time('e'),,3) 'seconds'; sayexitinclude Functionsinclude Sequencesinclude AbendFACTORS OF AN INTEGERREXX-Regina_3.9.6(MT) 5.00 29 Apr 2024 1 has 1 divisors: 1 2 has 2 divisors: 1 2 3 has 2 divisors: 1 3 4 has 3 divisors: 1 2 4 5 has 2 divisors: 1 5 6 has 4 divisors: 1 2 3 6 7 has 2 divisors: 1 7 8 has 4 divisors: 1 2 4 8 9 has 3 divisors: 1 3 9 10 has 4 divisors: 1 2 5 10 11 has 2 divisors: 1 11 12 has 6 divisors: 1 2 3 4 6 12 13 has 2 divisors: 1 13 14 has 4 divisors: 1 2 7 14 15 has 4 divisors: 1 3 5 15 16 has 5 divisors: 1 2 4 8 16 17 has 2 divisors: 1 17 18 has 6 divisors: 1 2 3 6 9 18 19 has 2 divisors: 1 19 20 has 6 divisors: 1 2 4 5 10 20 21 has 4 divisors: 1 3 7 21 22 has 4 divisors: 1 2 11 22 23 has 2 divisors: 1 23 24 has 8 divisors: 1 2 3 4 6 8 12 24 25 has 3 divisors: 1 5 25 26 has 4 divisors: 1 2 13 26 27 has 4 divisors: 1 3 9 27 28 has 6 divisors: 1 2 4 7 14 28 29 has 2 divisors: 1 29 30 has 8 divisors: 1 2 3 5 6 10 15 30 31 has 2 divisors: 1 31 32 has 6 divisors: 1 2 4 8 16 32 33 has 4 divisors: 1 3 11 33 34 has 4 divisors: 1 2 17 34 35 has 4 divisors: 1 5 7 35 36 has 9 divisors: 1 2 3 4 6 9 12 18 36 37 has 2 divisors: 1 37 38 has 4 divisors: 1 2 19 38 39 has 4 divisors: 1 3 13 39 40 has 8 divisors: 1 2 4 5 8 10 20 40 41 has 2 divisors: 1 41 42 has 8 divisors: 1 2 3 6 7 14 21 42 43 has 2 divisors: 1 43 44 has 6 divisors: 1 2 4 11 22 44 45 has 6 divisors: 1 3 5 9 15 45 46 has 4 divisors: 1 2 23 46 47 has 2 divisors: 1 47 48 has 10 divisors: 1 2 3 4 6 8 12 16 24 48 49 has 3 divisors: 1 7 49 50 has 6 divisors: 1 2 5 10 25 50 51 has 4 divisors: 1 3 17 51 52 has 6 divisors: 1 2 4 13 26 52 53 has 2 divisors: 1 53 54 has 8 divisors: 1 2 3 6 9 18 27 54 55 has 4 divisors: 1 5 11 55 56 has 8 divisors: 1 2 4 7 8 14 28 56 57 has 4 divisors: 1 3 19 57 58 has 4 divisors: 1 2 29 58 59 has 2 divisors: 1 59 60 has 12 divisors: 1 2 3 4 5 6 10 12 15 20 30 60 61 has 2 divisors: 1 61 62 has 4 divisors: 1 2 31 62 63 has 6 divisors: 1 3 7 9 21 63 64 has 7 divisors: 1 2 4 8 16 32 64 65 has 4 divisors: 1 5 13 65 66 has 8 divisors: 1 2 3 6 11 22 33 66 67 has 2 divisors: 1 67 68 has 6 divisors: 1 2 4 17 34 68 69 has 4 divisors: 1 3 23 69 70 has 8 divisors: 1 2 5 7 10 14 35 70 71 has 2 divisors: 1 71 72 has 12 divisors: 1 2 3 4 6 8 9 12 18 24 36 72 73 has 2 divisors: 1 73 74 has 4 divisors: 1 2 37 74 75 has 6 divisors: 1 3 5 15 25 75 76 has 6 divisors: 1 2 4 19 38 76 77 has 4 divisors: 1 7 11 77 78 has 8 divisors: 1 2 3 6 13 26 39 78 79 has 2 divisors: 1 79 80 has 10 divisors: 1 2 4 5 8 10 16 20 40 80 81 has 5 divisors: 1 3 9 27 81 82 has 4 divisors: 1 2 41 82 83 has 2 divisors: 1 83 84 has 12 divisors: 1 2 3 4 6 7 12 14 21 28 42 84 85 has 4 divisors: 1 5 17 85 86 has 4 divisors: 1 2 43 86 87 has 4 divisors: 1 3 29 87 88 has 8 divisors: 1 2 4 8 11 22 44 88 89 has 2 divisors: 1 89 90 has 12 divisors: 1 2 3 5 6 9 10 15 18 30 45 90 91 has 4 divisors: 1 7 13 91 92 has 6 divisors: 1 2 4 23 46 92 93 has 4 divisors: 1 3 31 93 94 has 4 divisors: 1 2 47 94 95 has 4 divisors: 1 5 19 95 96 has 12 divisors: 1 2 3 4 6 8 12 16 24 32 48 96 97 has 2 divisors: 1 97 98 has 6 divisors: 1 2 7 14 49 98 99 has 6 divisors: 1 3 9 11 33 99100 has 9 divisors: 1 2 4 5 10 20 25 50 1000.003 seconds
nArray = list(100)n = 45j = 0for i = 1 to n if n % i = 0 j = j + 1 nArray[j] = i oknextsee "Factors of " + n + " = "for i = 1 to j see "" + nArray[i] + " "next
≪ → n ≪ { } DUP 1 n √FOR dIF n d MOD NOTTHEN d + n d /IF DUP d ≠THEN ROT + SWAPELSE DROPENDENDNEXT SWAP + ≫ ≫'FACTS' STO45 FACTS53 FACTS64 FACTS
3: { 1 3 5 9 15 45 }2: { 1 53 }1: { 1 2 4 8 16 32 64 }class Integer def factors() (1..self).select { |n| (self % n).zero? } endendp 45.factors[1, 3, 5, 9, 15, 45]
As we only have to loop up to, we can write
class Integer def factors 1.upto(Integer.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i| f << self/i unless i == self/i f << i end.sort endend[45, 53, 64].each {|n| puts "#{n} : #{n.factors}"}45 : [1, 3, 5, 9, 15, 45]53 : [1, 53]64 : [1, 2, 4, 8, 16, 32, 64]
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 :*}. sortend[1, 7, 45, 100].each{|n| p factors n}Output:
[1][1, 7][1, 3, 5, 9, 15, 45][1, 2, 4, 5, 10, 20, 25, 50, 100]
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}Alternative functional version:
fn factor(n: i32) -> Vec<i32> { (1..=n).filter(|i| n % i == 0).collect()}class MAIN is factors!(n :INT):INT is yield 1; loop i ::= 2.upto!( n.flt.sqrt.int ); if n%i = 0 then yield i; if (i*i) /= n then yield n / i; end; end; end; yield n; end; main is a :ARRAY{INT} := |3135, 45, 64, 53, 45, 81|; loop l ::= a.elt!; #OUT + "factors of " + l + ": "; loop ri ::= factors!(l); #OUT + ri + " "; end; #OUT + "\n"; end; end;end;Brute force approach:
def factors(num: Int) = { (1 to num).filter { divisor => num % divisor == 0 }}Brute force until sqrt(num) is enough, the code above can be edited as follows (Scala 3 enabled)
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 / _)}This implementation uses a naive trial division algorithm.
(define (factors n) (define (*factors d) (cond ((> d n) (list)) ((= (modulo n d) 0) (cons d (*factors (+ d 1)))) (else (*factors (+ d 1))))) (*factors 1))(display (factors 1111111))(newline)
(1 239 4649 1111111)
$ include "seed7_05.s7i";const proc: writeFactors (in integer: number) is func local var integer: testNum is 0; begin write("Factors of " <& number <& ": "); for testNum range 1 to sqrt(number) do if number rem testNum = 0 then if testNum <> 1 then write(", "); end if; write(testNum); if testNum <> number div testNum then write(", " <& number div testNum); end if; end if; end for; writeln; end func;const proc: main is func local const array integer: numsToFactor is [] (45, 53, 64); var integer: number is 0; begin for number range numsToFactor do writeFactors(number); end for; end func;Factors of 45: 1, 45, 3, 15, 5, 9Factors of 53: 1, 53Factors of 64: 1, 64, 2, 32, 4, 16, 8
Brute Force Method
A simple brute force method using an indexed partial function as a filter.
Factors(num(0))[i] := i when num mod i = 0 foreach i within 1 ... num;
Slightly More Efficient Method
A slightly more efficient method, only going up to the sqrt(n).
Factors(num(0)) :=letfactorPairs[i] :=[i] when i = sqrt(num)else [i, num/i] when num mod i = 0 foreach i within 1 ... floor(sqrt(num));injoin(factorPairs);
Built-in:
say divisors(97) #=> [1, 97]say divisors(2695) #=> [1, 5, 7, 11, 35, 49, 55, 77, 245, 385, 539, 2695]
Trial-division (slow for large n):
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)}"}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]
n@(Integer traits) primeFactors[ [| :result | result nextPut: 1. n primesDo: [| :prime | result nextPut: prime]] writingAs: {}].whereprimesDo: is a part of the standard numerics library:
n@(Integer traits) primesDo: block"Decomposes the Integer into primes, applying the block to each (in increasingorder)."[| div next remaining | div: 2. next: 3. remaining: n. [[(remaining \\ div) isZero] whileTrue: [block applyTo: {div}.remaining: remaining // div]. remaining = 1] whileFalse: [div: next. next: next + 2] "Just looks at the next odd integer."].Copied from the Python example, but code added to the Integer built in class:
Integer>>factors| a |a := OrderedCollection new.1 to: (self / 2) do: [ :i | ((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)
Need to print the list because Standard ML truncates the display oflonger returned lists.
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;
Call:
printIntList(factors 12345)printIntList(factors 120)
1 3 5 15 823 2469 4115 123451 2 3 4 5 6 8 10 12 15 20 24 30 40 60
Simple implementation:
func factors(n: Int) -> [Int] { return filter(1...n) { n % $0 == 0 }}More efficient implementation:
import func Darwin.sqrtfunc sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }func factors(n: Int) -> [Int] { var result = [Int]() for factor in filter (1...sqrt(n), { n % $0 == 0 }) { result.append(factor) if n/factor != factor { result.append(n/factor) } } return sorted(result) }Call:
println(factors(4))println(factors(1))println(factors(25))println(factors(63))println(factors(19))println(factors(768))
[1, 2, 4][1][1, 5, 25][1, 3, 7, 9, 21, 63][1, 19][1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 768]
[1..351 -> \(when <?(351 mod $ <=0>)> do $! \)] -> !OUT::write
v0.5
[1..351 -> if <|?(351 mod $ matches <|=0>)>] !
[1, 3, 9, 13, 27, 39, 117, 351]
proc factors {n} { set factors {} for {set i 1} {$i <= sqrt($n)} {incr i} { if {$n % $i == 0} { lappend factors $i [expr {$n / $i}] } } return [lsort -unique -integer $factors]}puts [factors 64]puts [factors 45]puts [factors 53]1 2 4 8 16 32 641 3 5 9 15 451 53
Factors ← ◴⊂⟜(⇌÷)⊸(▽:⟜≡(=0◿)⊙¤⊸(↘1⇡+1⌊√))⍚Factors {45 53 64}{[1 3 5 9 15 45] [1 53] [1 2 4 8 16 32 64]}This should work in all Bourne-compatible shells, assuming the system has bothsort and at least one ofbc ordc.
factor() { r=`echo "sqrt($1)" | bc` # or `echo $1 v p | dc` i=1 while [ $i -lt $r ]; do if [ `expr $1 % $i` -eq 0 ]; then echo $i expr $1 / $i fi i=`expr $i + 1` done | sort -nu}This program takes an integer from the command line and outputs its factors.
decl int nset n (int args<1>)decl int ifor (set i 1) (< i (+ (/ n 2) 1)) (inc i) if (= (mod n i) 0) out i " " console end ifend forout n endl console
The simple way:
#import std#import natfactors "n" = (filter not remainder/"n") nrange(1,"n")
The complicated way:
factors "n" = nleq-<&@s <.~&r,quotient>*= "n"-* (not remainder/"n")*~ nrange(1,root("n",2))Another idea would be to approximate an upper bound for the square root of"n" with some bit twiddling such as&!*K31 "n", which evaluates to a binary number of all 1's half the width of "n" rounded up, and another would be to use thedivision 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
factors = nleq-<&@rrZPFLs+ ^(~&r,division)^*D/~& nrange/1+ &!*K31
wherenleq-<& isn't strictly necessary unless an ordered list is required.
#cast %nLexample = factors 100
<1,2,4,5,10,20,25,50,100>
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 ; endendmodule
45 => 1 3 5 9 15 45
@let { factors1 &n !-\%%n @to n factors_tacit @(\\%% !- @to) [[ !factors1 10 !factors_tacit 100 !factors1 720 ]]}Returns:
[ [1 2 5 10] [1 2 4 5 10 20 25 50 100] [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]]
fn main() {mut arr := []int{len: 100}mut n, mut j := 45, 0for 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]} ")}}Factors of 45 = 1 3 5 9 15 45
import "./fmt" for Fmtimport "./math" for Intvar 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))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]
section .bss factorArr resd 250 ;big buffer against seg fault section .textglobal _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
include c:\cxpl\codes;int N0, N, F;[N0:= 1;repeat IntOut(0, N0); Text(0, " = "); F:= 2; N:= N0; repeat if rem(N/F) = 0 then [if N # N0 then Text(0, " * "); IntOut(0, F); N:= N/F; ] else F:= F+1; until F>N; if N0=1 then IntOut(0, 1); \1 = 1 CrLf(0); N0:= N0+1;until KeyHit;]
1 = 12 = 23 = 34 = 2 * 25 = 56 = 2 * 37 = 78 = 2 * 2 * 29 = 3 * 310 = 2 * 511 = 1112 = 2 * 2 * 313 = 1314 = 2 * 715 = 3 * 516 = 2 * 2 * 2 * 217 = 1718 = 2 * 3 * 3. . .57086 = 2 * 17 * 23 * 7357087 = 3 * 3 * 634357088 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 22357089 = 5708957090 = 2 * 3 * 5 * 11 * 17357091 = 37 * 154357092 = 2 * 2 * 7 * 203957093 = 3 * 1903157094 = 2 * 2854757095 = 5 * 19 * 60157096 = 2 * 2 * 2 * 3 * 3 * 13 * 6157097 = 57097
fcn f(n){ (1).pump(n.toFloat().sqrt(), List, '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 comprehensionzkl: f(45)L(L(1,45),L(3,15),L(5,9))zkl: g(45)L(L(1,45),L(3,15),L(5,9))