# Factors of an integer

Factors of an integer
You are encouraged to solve this task according to the task description, using any language you may know.

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 the Basic Data Operations category, or:

Integer Operations
Arithmetic | Comparison

Boolean Operations
Bitwise | Logical

String Operations
Concatenation | Interpolation | Matching

Memory Operations

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 is 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 even prime numbers will have at least two factors; ‘1’ and themselves.

 <:1:~>|~#:end:>~x}:str:/={^:wei:~%x<:a:x=$~=}:wei:x<:1:+{>~>x=-#:fin:^:str:}:fin:{{~%  ## ACL2 (defun factors-r (n i) (declare (xargs :measure (nfix (- n i)))) (cond ((zp (- n i)) (list n)) ((= (mod n i) 0) (cons i (factors-r n (1+ i)))) (t (factors-r n (1+ i))))) (defun factors (n) (factors-r n 1)) ## ActionScript function factor(n:uint):Vector.<uint>{ var factors:Vector.<uint> = new Vector.<uint>(); for(var i:uint = 1; i <= n; i++) if(n % i == 0)factors.push(i); return factors;} ## Ada with Ada.Text_IO;with Ada.Command_Line;procedure Factors is Number : Positive; Test_Nr : Positive := 1;begin if Ada.Command_Line.Argument_Count /= 1 then Ada.Text_IO.Put (Ada.Text_IO.Standard_Error, "Missing argument!"); Ada.Command_Line.Set_Exit_Status (Ada.Command_Line.Failure); return; end if; Number := Positive'Value (Ada.Command_Line.Argument (1)); Ada.Text_IO.Put ("Factors of" & Positive'Image (Number) & ": "); loop if Number mod Test_Nr = 0 then Ada.Text_IO.Put (Positive'Image (Test_Nr) & ","); end if; exit when Test_Nr ** 2 >= Number; Test_Nr := Test_Nr + 1; end loop; Ada.Text_IO.Put_Line (Positive'Image (Number) & ".");end Factors; ## Aikido import math function 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)) ## ALGOL 68 Works with: ALGOL 68 version Revision 1 - no extensions to language used Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d Note: The following implements generators, eliminating the need of declaring arbitrarily long int 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 Output:  +45: 1, 45, 3, 15, 5, 9 +53: 1, 53 +64: 1, 64, 2, 32, 4, 16, 8  ## APL  factors←{(0=(⍳⍵)|⍵)/⍳⍵} factors 123451 3 5 15 823 2469 4115 12345 factors 7201 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 ## AutoHotkey 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, N U D, Return, v} Output: 1,3,5,9,15,45 1,53 1,2,4,8,16,32,64 ## AutoIt ;AutoIt Version: 3.2.10.0$num = 45MsgBox (0,"Factors", "Factors of " & $num & " are: " & factors($num))consolewrite ("Factors of " & $num & " are: " & factors($num))Func factors($intg)$ls_factors=""   For $i = 1 to$intg/2      if ($intg/$i - int($intg/$i))=0 Then	 $ls_factors=$ls_factors&$i &", " EndIf Next Return$ls_factors&$intgEndFunc Output: Factors of 45 are: 1, 3, 5, 9, 15, 45  ## AWK  # 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 =$0    printf("factors of %s:",n)    for (i=1; i<=n; i++) {      if (n % i == 0) {        printf(" %d",i)      }    }    printf("\n")}

output:

enter a number or C/R to exit
invalid: -1
factors of 0:
factors of 1: 1
factors of 2: 1 2
factors of 11: 1 11
factors of 64: 1 2 4 8 16 32 64
factors of 100: 1 2 4 5 10 20 25 50 100
factors of 32766: 1 2 3 6 43 86 127 129 254 258 381 762 5461 10922 16383 32766
factors of 32767: 1 7 31 151 217 1057 4681 32767


## BASIC

Works with: QBasic

This example stores the factors in a shared array (with the original number as the last element) for later retrieval.

Note that this will error out if you pass 32767 (or higher).

DECLARE SUB factor (what AS INTEGER) REDIM SHARED factors(0) AS INTEGER DIM i AS INTEGER, L AS INTEGER INPUT "Gimme a number"; i factor i PRINT factors(0);FOR L = 1 TO UBOUND(factors)    PRINT ","; factors(L);NEXTPRINT SUB factor (what AS INTEGER)    DIM tmpint1 AS INTEGER    DIM L0 AS INTEGER, L1 AS INTEGER     REDIM tmp(0) AS INTEGER    REDIM factors(0) AS INTEGER    factors(0) = 1     FOR L0 = 2 TO what        IF (0 = (what MOD L0)) THEN            'all this REDIMing and copying can be replaced with:            'REDIM PRESERVE factors(UBOUND(factors)+1)            'in languages that support the PRESERVE keyword            REDIM tmp(UBOUND(factors)) AS INTEGER            FOR L1 = 0 TO UBOUND(factors)                tmp(L1) = factors(L1)            NEXT            REDIM factors(UBOUND(factors) + 1)            FOR L1 = 0 TO UBOUND(factors) - 1                factors(L1) = tmp(L1)            NEXT            factors(UBOUND(factors)) = L0        END IF    NEXTEND SUB

Sample outputs:

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


## Batch File

Command line version:

@echo offset res=Factors of %1:for /L %%i in (1,1,%1) do call :fac %1 %%iecho %res%goto :eof :facset /a test = %1 %% %2if %test% equ 0 set res=%res% %2

Outputs:

>factors 32767
Factors of 32767: 1 7 31 151 217 1057 4681 32767

>factors 45
Factors of 45: 1 3 5 9 15 45

>factors 53
Factors of 53: 1 53

>factors 64
Factors of 64: 1 2 4 8 16 32 64

>factors 100
Factors of 100: 1 2 4 5 10 20 25 50 100

Interactive version:

@echo offset /p limit=Gimme a number:set res=Factors of %limit%:for /L %%i in (1,1,%limit%) do call :fac %limit% %%iecho %res%goto :eof :facset /a test = %1 %% %2if %test% equ 0 set res=%res% %2

Outputs:

>factors
Gimme a number:27
Factors of 27: 1 3 9 27

>factors
Gimme a number:102
Factors of 102: 1 2 3 6 17 34 51 102

## Forth

This is a slightly optimized algorithm, since it realizes there are no factors between n/2 and n. The values are saved on the stack and - in true Forth fashion - printed in descending order.

: factors dup 2/ 1+ 1 do dup i mod 0= if i swap then loop ;: .factors factors begin dup dup . 1 <> while drop repeat drop cr ;  45 .factors53 .factors64 .factors100 .factors

## Fortran

Works with: Fortran version 90 and later
program Factors  implicit none  integer :: i, number   write(*,*) "Enter a number between 1 and 2147483647"  read*, number   do i = 1, int(sqrt(real(number))) - 1    if (mod(number, i) == 0) write (*,*) i, number/i  end do   ! Check to see if number is a square  i = int(sqrt(real(number)))   if (i*i == number) then     write (*,*) i  else if (mod(number, i) == 0) then     write (*,*) i, number/i  end if end program

## GAP

# 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 -> n mod k = 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)                                                local f, p;  f := Collected(FactorsInt(n));  p := List(f, v -> List([0 .. v[2]], k -> v[1]^k));  return SortedList(List(Cartesian(p), Product));end; div2(Factorial(5));# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]

## Go

Trial division, no prime number generator, but with some optimizations. It's good enough to factor any 64 bit integer, with large primes taking several seconds.

package main import "fmt" func main() {    printFactors(-1)    printFactors(0)    printFactors(1)    printFactors(2)    printFactors(3)    printFactors(53)    printFactors(45)    printFactors(64)    printFactors(600851475143)    printFactors(999999999999999989)} func printFactors(nr int64) {    if nr < 1 {        fmt.Println("\nFactors of", nr, "not computed")        return    }    fmt.Printf("\nFactors of %d: ", nr)    fs := make([]int64, 1)    fs[0] = 1    apf := func(p int64, e int) {        n := len(fs)        for i, pp := 0, p; i < e; i, pp = i+1, pp*p {            for j := 0; j < n; j++ {                fs = append(fs, fs[j]*pp)            }        }    }    e := 0    for ; nr & 1 == 0; e++ {        nr >>= 1    }    apf(2, e)    for d := int64(3); nr > 1; d += 2 {        if d*d > nr {            d = nr        }        for e = 0; nr%d == 0; e++ {            nr /= d        }        if e > 0 {            apf(d, e)        }    }    fmt.Println(fs)    fmt.Println("Number of factors =", len(fs))}

Output:

Factors of -1 not computed

Factors of 0 not computed

Factors of 1: [1]
Number of factors = 1

Factors of 2: [1 2]
Number of factors = 2

Factors of 3: [1 3]
Number of factors = 2

Factors of 53: [1 53]
Number of factors = 2

Factors of 45: [1 3 9 5 15 45]
Number of factors = 6

Factors of 64: [1 2 4 8 16 32 64]
Number of factors = 7

Factors of 600851475143: [1 71 839 59569 1471 104441 1234169 87625999 6857 486847 5753023 408464633 10086647 716151937 8462696833 600851475143]
Number of factors = 16

Factors of 999999999999999989: [1 999999999999999989]
Number of factors = 2

## Groovy

A straight brute force approach up to the square root of N:

def factorize = { long target ->      if (target == 1) return [1L]     if (target < 4) return [1L, target]     def targetSqrt = Math.sqrt(target)    def lowfactors = (2L..targetSqrt).grep { (target % it) == 0 }    if (lowfactors == []) return [1L, target]    def nhalf = 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)]) }

Output:

[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]]

Using D. Amos module Primes [1] for finding prime factors

import HFM.Primes(primePowerFactors)import Data.List factors = map product.          mapM (uncurry((. enumFromTo 0) . map .(^) )) . primePowerFactors

###  List comprehension

Naive, functional, no import

factors_naive n = [i | i <-[1..n], (mod n i) == 0]
factors_naive 6[1,2,3,6]

Factor, cofactor. Rearrange a list of tuples to a sorted list

import Data.Listtuple_to_list lt = (fst lt) ++ (snd lt)factors_co n = sort (tuple_to_list(unzip         [ (j, (div n j)) | j <-                 [i | i <-                         [1..truncate (sqrt (fromIntegral n))]                        , (mod n i) == 0]] ))
factors_co 6[1,2,3,6]

## HicEst

 DLG(NameEdit=N, TItle='Enter an integer')  DO i = 1, N^0.5   IF( MOD(N,i) == 0) WRITE() i, N/i ENDDO END

## Icon and Unicon

procedure main(arglist)numbers := arglist ||| [ 32767, 45, 53, 64, 100]    # combine command line provided and default set of valuesevery writes(lf,"factors of ",i := !numbers,"=") & writes(divisors(i)," ") do lf := "\n"end link factors

Sample Output:

factors of 32767=1 7 31 151 217 1057 4681 32767
factors of 45=1 3 5 9 15 45
factors of 53=1 53
factors of 64=1 2 4 8 16 32 64
factors of 100=1 2 4 5 10 20 25 50 100
divisors

## J

J has a primitive, q: which returns its prime factors.

q: 40 2 2 2 5

Alternatively, q: can produce provide a table of the exponents of the unique relevant prime factors

   __ q: 4202 3 5 72 1 1 1

With this, we can form lists of each of the potential relevant powers of each of these prime factors

   ((^ i.@>:)&.>/) __ q: 420┌─────┬───┬───┬───┐│1 2 4│1 3│1 5│1 7│└─────┴───┴───┴───┘

From here, it's a simple matter (*/&>@{) to compute all possible factors of the original number

factrs=: */&>@{@((^ i.@>:)&.>/)@q:~&__   factrs 40 1  5 2 10 4 20 8 40

However, a data structure which is organized around the prime decomposition of the argument can be hard to read. So, for reader convenience, we should probably arrange them in a monotonically increasing list:

   factors=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__   factors 4201 2 3 4 5 6 7 10 12 14 15 20 21 28 30 35 42 60 70 84 105 140 210 420

A less efficient, but concise variation on this theme:

    ~.,*/&> { 1 ,&.> q: 401 5 2 10 4 20 8 40

This computes 2^n intermediate values where n is the number of prime factors of the original number.

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:~&__

## Java

Works with: Java version 5+
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;}

## JavaScript

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]

## Julia

function factors(n)    f = [one(n)]    for (p,e) in factor(n)        f = reduce(vcat, f, [f*p^j for j in 1:e])    end    return length(f) == 1 ? [one(n), n] : sort!(f)end

Example output:

julia> factors(45)
6-element Array{Int64,1}:
1
3
5
9
15
45


## K

   f:{d:&~x!'!1+_sqrt x;?d,_ x%|d}    f 11    f 31 3    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 24

## Liberty BASIC

num = 10677106534462215678539721403561279maxnFactors = 1000dim primeFactors(maxnFactors),  nPrimeFactors(maxnFactors)global nDifferentPrimeNumbersFound, nFactors, iFactor  print "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 i print "done" wait  function factorize(iNum,offset)    factorFound=0    i = offset    do        if (iNum MOD i)=0 _        then            if primeFactors(nDifferentPrimeNumbersFound) = i _            then               nPrimeFactors(nDifferentPrimeNumbersFound) = nPrimeFactors(nDifferentPrimeNumbersFound) + 1            else               nDifferentPrimeNumbersFound = nDifferentPrimeNumbersFound + 1               primeFactors(nDifferentPrimeNumbersFound) = i               nPrimeFactors(nDifferentPrimeNumbersFound) = 1            end if            if iNum/i<>1 then dummy = factorize(iNum/i,i)            factorFound=1         end if         i=i+1    loop while factorFound=0 and i<=sqr(iNum)    if factorFound=0 _    then       nDifferentPrimeNumbersFound = nDifferentPrimeNumbersFound + 1       primeFactors(nDifferentPrimeNumbersFound) = iNum       nPrimeFactors(nDifferentPrimeNumbersFound) = 1    end ifend function  function showPrimeFactors(iNum)   showPrimeFactors=1   print iNum;" = ";   for i=1 to nDifferentPrimeNumbersFound      print primeFactors(i);"^";nPrimeFactors(i);      if i<nDifferentPrimeNumbersFound then print " * "; else print ""      showPrimeFactors = showPrimeFactors*(nPrimeFactors(i)+1)   next i   end function  function generateFactors(product,pIndex)   if pIndex>nDifferentPrimeNumbersFound _   then      factors(iFactor) = product      iFactor=iFactor+1   else      for i=0 to nPrimeFactors(pIndex)         dummy = generateFactors(product*primeFactors(pIndex)^i,pIndex+1)      next i   end if   end function

Outcome:

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

## Logo

to factors :n  output filter [equal? 0 modulo :n ?] iseq 1 :nend show factors 28       ; [1 2 4 7 14 28]

## Lua

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

## Mathematica

Factorize[n_Integer] := Divisors[n]

## MATLAB / Octave

  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;

Output:

>> 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


## Maxima

The builtin divisors 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))));

## Mercury

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 predicate factor/2 and in the function factor/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:

1. The input number itself and 1 are both considered factors.
2. The numbers between 2 and the square root of the input number are checked for even division.
3. If the incremental number divides evenly into the input number, both the incremental number and the quotient are added to the list of factors.

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.

### fac.m

:- 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 and output

Use of the code looks like this:

## NetRexx

Translation of: REXX
/* 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)      End method 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           */

Output:

java divl 1 10
1 -> 1
2 -> 1 2
3 -> 1 3
4 -> 1 2 4
5 -> 1 5
6 -> 1 2 3 6
7 -> 1 7
8 -> 1 2 4 8
9 -> 1 3 9
10 -> 1 2 5 10

## Niue

[ '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 )

## Oberon-2

Oxford Oberon-2

 MODULE Factors;IMPORT Out,SYSTEM;TYPE		LIPool = POINTER TO ARRAY OF LONGINT;	LIVector= POINTER TO LIVectorDesc;	LIVectorDesc = RECORD		cap: INTEGER;		len: INTEGER;		LIPool: LIPool;	END; 	PROCEDURE New(cap: INTEGER): LIVector;	VAR		v: LIVector;	BEGIN		NEW(v);		v.cap := cap;		v.len := 0;		NEW(v.LIPool,cap);		RETURN v	END New; 	PROCEDURE (v: LIVector) Add(x: LONGINT);	VAR 		newLIPool: LIPool;	BEGIN		IF 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 := newLIPool		END;		v.LIPool[v.len] := x;		INC(v.len)	END Add; 	PROCEDURE (v: LIVector) At(idx: INTEGER): LONGINT;	BEGIN		RETURN v.LIPool[idx];	END At;  PROCEDURE Factors(n:LONGINT): LIVector;VAR 	j: LONGINT;	v: LIVector;BEGIN	v := New(16);	FOR j := 1 TO n DO		IF (n MOD j) = 0 THEN v.Add(j) END;	END; 	RETURN vEND Factors; VAR	v: LIVector;	j: INTEGER;BEGIN	v := Factors(123);	FOR j := 0 TO v.len - 1 DO		Out.LongInt(v.At(j),4);Out.Ln	END;	Out.Int(v.len,6);Out.String(" factors");Out.LnEND Factors.

Output:


1
3
41
123
4 factors


## Objeck

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();      };    }  }}

## OCaml

let rec range = function 0 -> [] | n -> range(n-1) @ [n] let factors n =  List.filter (fun v -> (n mod v) = 0) (range n)

## Oz

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}}

## PARI/GP

divisors(n)

## Pascal

Translation of: Fortran
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.

Output:

Enter a number between 1 and 2147483647: 49
1 49 7

Enter a number between 1 and 2147483647: 353435
1 25755 3 8585 5 5151 15 1717 17 1515 51 505 85 303 101 255



## Perl

sub factors{        my($n) = @_; return grep {$n % $_ == 0 }(1 ..$n);}print join ' ',factors(64);

## Perl 6

Works with: Rakudo Star version 2013-10
sub factors (Int $n) { sort uniq map {$^x, $n div$^x },    grep { $n %%$^x },    1 .. sqrt $n;} ## PHP 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;} ## PicoLisp (de factors (N) (filter '((D) (=0 (% N D))) (range 1 N) ) ) ## PL/I do i = 1 to n; if mod(n, i) = 0 then put skip list (i);end; ## PowerShell ### Straightforward but slow 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 the Where-Object cmdlet. It's very slow though, so it is not very usable for larger numbers. ### A little more clever 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.

## ProDOS

Uses the math module:

editvar /newvar /value=a /userinput=1 /title=Enter an integer:do /delimspaces %% -a- >bprintline Factors of -a-: -b- 

## Prolog

factor(N, L) :-	factor(N, 1, [], L). factor(N, X, LC, L) :-	0 is N mod X,	!,	Q is N / X,	(Q = X ->	    sort([Q | LC], L)	;	    (Q > X ->	       X1 is X+1,	       factor(N, X1, [X, Q|LC], L)	    ;	      sort(LC, L)	    )	). factor(N, X, LC, L) :-	Q is N / X,	(Q > X ->	    X1 is X+1,	    factor(N, X1, LC, L)	;	    sort(LC, L)	).

Output :

 ?- factor(36, L).
L = [1,2,3,4,6,9,12,18,36].

?- factor(53, L).
L = [1,53].

?- factor(32765, L).
L = [1,5,6553,32765].

?- factor(32766, L).
L = [1,2,3,6,43,86,127,129,254,258,381,762,5461,10922,16383,32766].

?- factor(32767, L).
L = [1,7,31,151,217,1057,4681,32767].

## PureBasic

Procedure PrintFactors(n)  Protected i, lim=Round(sqr(n),#PB_Round_Up)  NewList F.i()  For i=1 To lim    If n%i=0      AddElement(F()): F()=i      AddElement(F()): F()=n/i    EndIf  Next  ;- Present the result  SortList(F(),#PB_Sort_Ascending)  ForEach F()    Print(str(F())+" ")  NextEndProcedure If OpenConsole()  Print("Enter integer to factorize: ")  PrintFactors(Val(Input()))  Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input()EndIf

Output can look like

Enter integer to factorize: 96
1 2 3 4 6 8 12 16 24 32 48 96


## Python

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 sqrt>>> def factor(n):      factors = set()      for x in range(1, int(sqrt(n)) + 1):        if n % x == 0:          factors.add(x)          factors.add(n//x)      return sorted(factors) >>> for 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:

def factor(n):	a, r = 1, [1]	while a * a < n:		a += 1		if n % a: continue		b, f = 1, []		while n % a == 0:			n //= a			b *= a			f += [i * b for i in r]		r += f	if n > 1: r += [i * n for i in r]	return r

## R

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  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


## Racket

 #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 

## REALbasic

Function factors(num As UInt64) As UInt64()  'This function accepts an unsigned 64 bit integer as input and returns an array of unsigned 64 bit integers  Dim result() As UInt64  Dim iFactor As UInt64 = 1  While iFactor <= num/2 'Since a factor will never be larger than half of the number    If num Mod iFactor = 0 Then      result.Append(iFactor)    End If    iFactor = iFactor + 1  Wend  result.Append(num) 'Since a given number is always a factor of itself  Return resultEnd Function

## REXX

### optimized version

This REXX version has no effective limits on the number of digits in the number to be factored   [by adjusting the number of digits (precision)].
It also indicates primes in the output.

/*REXX program displays (in order) the  divisors of positive integer(s).*/@.=left('',7);   @.1='{unity}';   @.2='[prime]'    /*unity & prime tags.*/parse arg low high step .                          /*get optional args. */high=word(high low 20,1);  low=word(low 1,1); step=word(step 1,1) /*opts*/w=length(high)+1;  numeric digits max(9,w)         /*'nuff digs for // ?*/say center('n',1+w)  '#divisors'  center('divisors',60)     /*header.   */say copies('─',1+w)  '─────────'  copies('─',60)            /*separator.*/      do n=low  to high  by step;    divs=divisors(n);     #=words(divs)     say  right(n,w)" "    center('('#")",9)    "──► "    @.#   ' '   divs     end   /*n*/exit                                   /*stick a fork in it, we're done.*//*──────────────────────────────────DIVISORS subroutine─────────────────*/divisors: procedure; parse arg x 1 b;  if x=1 then return 1;   odd=x//2a=1                                    /* [↓] use only EVEN or ODD ints.*/   do j=2+odd  by 1+odd  while j*j<x   /*divide by all integers up to √x*/   if x//j==0  then do; a=a j; b=x%j b; end /*add divs to α&ß lists if ÷*/   end   /*j*/                         /* [↑]  %  is REXX integer divide*/                                       /* [↓] adjust for square.      _ */if j*j==x  then  return  a j b         /*Was X a square?  If so, add √x.*/                 return  a   b         /*return divisors  (both lists). */

output when the input used is: 1 200

  n   #divisors                           divisors
───── ───────── ────────────────────────────────────────────────────────────
1     (1)    ──►  {unity}   1
2     (2)    ──►  [prime]   1 2
3     (2)    ──►  [prime]   1 3
4     (3)    ──►            1 2 4
5     (2)    ──►  [prime]   1 5
6     (4)    ──►            1 2 3 6
7     (2)    ──►  [prime]   1 7
8     (4)    ──►            1 2 4 8
9     (3)    ──►            1 3 9
10     (4)    ──►            1 2 5 10
11     (2)    ──►  [prime]   1 11
12     (6)    ──►            1 2 3 4 6 12
13     (2)    ──►  [prime]   1 13
14     (4)    ──►            1 2 7 14
15     (4)    ──►            1 3 5 15
16     (5)    ──►            1 2 4 8 16
17     (2)    ──►  [prime]   1 17
18     (6)    ──►            1 2 3 6 9 18
19     (2)    ──►  [prime]   1 19
20     (6)    ──►            1 2 4 5 10 20
21     (4)    ──►            1 3 7 21
22     (4)    ──►            1 2 11 22
23     (2)    ──►  [prime]   1 23
24     (8)    ──►            1 2 3 4 6 8 12 24
25     (3)    ──►            1 5 25
26     (4)    ──►            1 2 13 26
27     (4)    ──►            1 3 9 27
28     (6)    ──►            1 2 4 7 14 28
29     (2)    ──►  [prime]   1 29
30     (8)    ──►            1 2 3 5 6 10 15 30
31     (2)    ──►  [prime]   1 31
32     (6)    ──►            1 2 4 8 16 32
33     (4)    ──►            1 3 11 33
34     (4)    ──►            1 2 17 34
35     (4)    ──►            1 5 7 35
36     (9)    ──►            1 2 3 4 6 9 12 18 36
37     (2)    ──►  [prime]   1 37
38     (4)    ──►            1 2 19 38
39     (4)    ──►            1 3 13 39
40     (8)    ──►            1 2 4 5 8 10 20 40
41     (2)    ──►  [prime]   1 41
42     (8)    ──►            1 2 3 6 7 14 21 42
43     (2)    ──►  [prime]   1 43
44     (6)    ──►            1 2 4 11 22 44
45     (6)    ──►            1 3 5 9 15 45
46     (4)    ──►            1 2 23 46
47     (2)    ──►  [prime]   1 47
48    (10)    ──►            1 2 3 4 6 8 12 16 24 48
49     (3)    ──►            1 7 49
50     (6)    ──►            1 2 5 10 25 50
51     (4)    ──►            1 3 17 51
52     (6)    ──►            1 2 4 13 26 52
53     (2)    ──►  [prime]   1 53
54     (8)    ──►            1 2 3 6 9 18 27 54
55     (4)    ──►            1 5 11 55
56     (8)    ──►            1 2 4 7 8 14 28 56
57     (4)    ──►            1 3 19 57
58     (4)    ──►            1 2 29 58
59     (2)    ──►  [prime]   1 59
60    (12)    ──►            1 2 3 4 5 6 10 12 15 20 30 60
61     (2)    ──►  [prime]   1 61
62     (4)    ──►            1 2 31 62
63     (6)    ──►            1 3 7 9 21 63
64     (7)    ──►            1 2 4 8 16 32 64
65     (4)    ──►            1 5 13 65
66     (8)    ──►            1 2 3 6 11 22 33 66
67     (2)    ──►  [prime]   1 67
68     (6)    ──►            1 2 4 17 34 68
69     (4)    ──►            1 3 23 69
70     (8)    ──►            1 2 5 7 10 14 35 70
71     (2)    ──►  [prime]   1 71
72    (12)    ──►            1 2 3 4 6 8 9 12 18 24 36 72
73     (2)    ──►  [prime]   1 73
74     (4)    ──►            1 2 37 74
75     (6)    ──►            1 3 5 15 25 75
76     (6)    ──►            1 2 4 19 38 76
77     (4)    ──►            1 7 11 77
78     (8)    ──►            1 2 3 6 13 26 39 78
79     (2)    ──►  [prime]   1 79
80    (10)    ──►            1 2 4 5 8 10 16 20 40 80
81     (5)    ──►            1 3 9 27 81
82     (4)    ──►            1 2 41 82
83     (2)    ──►  [prime]   1 83
84    (12)    ──►            1 2 3 4 6 7 12 14 21 28 42 84
85     (4)    ──►            1 5 17 85
86     (4)    ──►            1 2 43 86
87     (4)    ──►            1 3 29 87
88     (8)    ──►            1 2 4 8 11 22 44 88
89     (2)    ──►  [prime]   1 89
90    (12)    ──►            1 2 3 5 6 9 10 15 18 30 45 90
91     (4)    ──►            1 7 13 91
92     (6)    ──►            1 2 4 23 46 92
93     (4)    ──►            1 3 31 93
94     (4)    ──►            1 2 47 94
95     (4)    ──►            1 5 19 95
96    (12)    ──►            1 2 3 4 6 8 12 16 24 32 48 96
97     (2)    ──►  [prime]   1 97
98     (6)    ──►            1 2 7 14 49 98
99     (6)    ──►            1 3 9 11 33 99
100     (9)    ──►            1 2 4 5 10 20 25 50 100
101     (2)    ──►  [prime]   1 101
102     (8)    ──►            1 2 3 6 17 34 51 102
103     (2)    ──►  [prime]   1 103
104     (8)    ──►            1 2 4 8 13 26 52 104
105     (8)    ──►            1 3 5 7 15 21 35 105
106     (4)    ──►            1 2 53 106
107     (2)    ──►  [prime]   1 107
108    (12)    ──►            1 2 3 4 6 9 12 18 27 36 54 108
109     (2)    ──►  [prime]   1 109
110     (8)    ──►            1 2 5 10 11 22 55 110
111     (4)    ──►            1 3 37 111
112    (10)    ──►            1 2 4 7 8 14 16 28 56 112
113     (2)    ──►  [prime]   1 113
114     (8)    ──►            1 2 3 6 19 38 57 114
115     (4)    ──►            1 5 23 115
116     (6)    ──►            1 2 4 29 58 116
117     (6)    ──►            1 3 9 13 39 117
118     (4)    ──►            1 2 59 118
119     (4)    ──►            1 7 17 119
120    (16)    ──►            1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
121     (3)    ──►            1 11 121
122     (4)    ──►            1 2 61 122
123     (4)    ──►            1 3 41 123
124     (6)    ──►            1 2 4 31 62 124
125     (4)    ──►            1 5 25 125
126    (12)    ──►            1 2 3 6 7 9 14 18 21 42 63 126
127     (2)    ──►  [prime]   1 127
128     (8)    ──►            1 2 4 8 16 32 64 128
129     (4)    ──►            1 3 43 129
130     (8)    ──►            1 2 5 10 13 26 65 130
131     (2)    ──►  [prime]   1 131
132    (12)    ──►            1 2 3 4 6 11 12 22 33 44 66 132
133     (4)    ──►            1 7 19 133
134     (4)    ──►            1 2 67 134
135     (8)    ──►            1 3 5 9 15 27 45 135
136     (8)    ──►            1 2 4 8 17 34 68 136
137     (2)    ──►  [prime]   1 137
138     (8)    ──►            1 2 3 6 23 46 69 138
139     (2)    ──►  [prime]   1 139
140    (12)    ──►            1 2 4 5 7 10 14 20 28 35 70 140
141     (4)    ──►            1 3 47 141
142     (4)    ──►            1 2 71 142
143     (4)    ──►            1 11 13 143
144    (15)    ──►            1 2 3 4 6 8 9 12 16 18 24 36 48 72 144
145     (4)    ──►            1 5 29 145
146     (4)    ──►            1 2 73 146
147     (6)    ──►            1 3 7 21 49 147
148     (6)    ──►            1 2 4 37 74 148
149     (2)    ──►  [prime]   1 149
150    (12)    ──►            1 2 3 5 6 10 15 25 30 50 75 150
151     (2)    ──►  [prime]   1 151
152     (8)    ──►            1 2 4 8 19 38 76 152
153     (6)    ──►            1 3 9 17 51 153
154     (8)    ──►            1 2 7 11 14 22 77 154
155     (4)    ──►            1 5 31 155
156    (12)    ──►            1 2 3 4 6 12 13 26 39 52 78 156
157     (2)    ──►  [prime]   1 157
158     (4)    ──►            1 2 79 158
159     (4)    ──►            1 3 53 159
160    (12)    ──►            1 2 4 5 8 10 16 20 32 40 80 160
161     (4)    ──►            1 7 23 161
162    (10)    ──►            1 2 3 6 9 18 27 54 81 162
163     (2)    ──►  [prime]   1 163
164     (6)    ──►            1 2 4 41 82 164
165     (8)    ──►            1 3 5 11 15 33 55 165
166     (4)    ──►            1 2 83 166
167     (2)    ──►  [prime]   1 167
168    (16)    ──►            1 2 3 4 6 7 8 12 14 21 24 28 42 56 84 168
169     (3)    ──►            1 13 169
170     (8)    ──►            1 2 5 10 17 34 85 170
171     (6)    ──►            1 3 9 19 57 171
172     (6)    ──►            1 2 4 43 86 172
173     (2)    ──►  [prime]   1 173
174     (8)    ──►            1 2 3 6 29 58 87 174
175     (6)    ──►            1 5 7 25 35 175
176    (10)    ──►            1 2 4 8 11 16 22 44 88 176
177     (4)    ──►            1 3 59 177
178     (4)    ──►            1 2 89 178
179     (2)    ──►  [prime]   1 179
180    (18)    ──►            1 2 3 4 5 6 9 10 12 15 18 20 30 36 45 60 90 180
181     (2)    ──►  [prime]   1 181
182     (8)    ──►            1 2 7 13 14 26 91 182
183     (4)    ──►            1 3 61 183
184     (8)    ──►            1 2 4 8 23 46 92 184
185     (4)    ──►            1 5 37 185
186     (8)    ──►            1 2 3 6 31 62 93 186
187     (4)    ──►            1 11 17 187
188     (6)    ──►            1 2 4 47 94 188
189     (8)    ──►            1 3 7 9 21 27 63 189
190     (8)    ──►            1 2 5 10 19 38 95 190
191     (2)    ──►  [prime]   1 191
192    (14)    ──►            1 2 3 4 6 8 12 16 24 32 48 64 96 192
193     (2)    ──►  [prime]   1 193
194     (4)    ──►            1 2 97 194
195     (8)    ──►            1 3 5 13 15 39 65 195
196     (9)    ──►            1 2 4 7 14 28 49 98 196
197     (2)    ──►  [prime]   1 197
198    (12)    ──►            1 2 3 6 9 11 18 22 33 66 99 198
199     (2)    ──►  [prime]   1 199
200    (12)    ──►            1 2 4 5 8 10 20 25 40 50 100 200


### Alternate Version

/* 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)  endexit divs: 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           */

## Ruby

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 $\sqrt{n}$, we can write

class Integer  def factors()    1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i|       f << i      f << self/i unless i == self/i      f    end.sort  endend[45, 53, 64].each {|n| p n.factors}

output

[1, 3, 5, 9, 15, 45]
[1, 53]
[1, 2, 4, 8, 16, 32, 64]

## Run BASIC

PRINT "Factors of 45 are ";factorlist$(45)PRINT "Factors of 12345 are "; factorlist$(12345)END function factorlist$(f)DIM L(100)FOR i = 1 TO SQR(f) IF (f MOD i) = 0 THEN L(c) = i c = c + 1 IF (f <> i^2) THEN L(c) = (f / i) c = c + 1 END IF END IFNEXT is = 1while s = 1s = 0for i = 0 to c-1 if L(i) > L(i+1) and L(i+1) <> 0 then t = L(i) L(i) = L(i+1) L(i+1) = t s = 1 end ifnext iwendFOR i = 0 TO c-1 factorlist$ = factorlist$+ STR$(L(i)) + ", "NEXTend function

output

Factors of 45 are 1, 3, 5, 9, 15, 45,
Factors of 12345 are 1, 3, 5, 15, 823, 2469, 4115, 12345, 

## Sather

Translation of: C++
class MAIN is   factors(n :INT):ARRAY{INT} is    f:ARRAY{INT};    f := #;    f := f.append(|1|);     f := f.append(|n|);    loop i ::= 2.upto!( n.flt.sqrt.int );      if n%i = 0 then        f := f.append(|i|);	if (i*i) /= n then f := f.append(|n / i|); end;      end;    end;    f.sort;    return f;  end;   main is    a :ARRAY{INT} := |3135, 45, 64, 53, 45, 81|;    loop l ::= a.elt!;      #OUT + "factors of " + l + ": ";      r ::= factors(l);      loop ri ::= r.elt!;        #OUT + ri + " ";      end;      #OUT + "\n";    end;  end;end;

## Scala

   def factors(num: Int) = {    (1 to num).filter { divisor =>      num % divisor == 0    }  }

## Scheme

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)

Output:

(1 239 4649 1111111)


## Ursala

The simple way:

#import std#import nat factors "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 the division 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

where nleq-<& isn't strictly necessary unless an ordered list is required.

#cast %nL example = factors 100

output:

<1,2,4,5,10,20,25,50,100>

## XPL0

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;]

Example output:

1 = 1
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
11 = 11
12 = 2 * 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 * 2 * 2 * 2
17 = 17
18 = 2 * 3 * 3
. . .
57086 = 2 * 17 * 23 * 73
57087 = 3 * 3 * 6343
57088 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 223
57089 = 57089
57090 = 2 * 3 * 5 * 11 * 173
57091 = 37 * 1543
57092 = 2 * 2 * 7 * 2039
57093 = 3 * 19031
57094 = 2 * 28547
57095 = 5 * 19 * 601
57096 = 2 * 2 * 2 * 3 * 3 * 13 * 61
57097 = 57097
`