Factors of an integer: Difference between revisions

Content added Content deleted

Inline

Revision as of 08:06, 9 January 2016

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.

0815

360 Assembly

Very compact version. <lang 360asm>* Factors of an integer - 07/10/2015 FACTOR CSECT

        USING  FACTOR,R15         set base register
        LA     R7,PG              pgi=@pg
        LA     R6,1               i
        L      R3,N               loop count

LOOP L R5,N n

        LA     R4,0
        DR     R4,R6              n/i
        LTR    R4,R4              if mod(n,i)=0
        BNZ    NEXT
        XDECO  R6,PG+120          edit i
        MVC    0(6,R7),PG+126     output i
        LA     R7,6(R7)           pgi=pgi+6

NEXT LA R6,1(R6) i=i+1

        BCT    R3,LOOP            loop
        XPRNT  PG,120             print buffer
        XR     R15,R15            set return code
        BR     R14                return to caller

N DC F'12345' <== input value PG DC CL132' ' buffer

        YREGS
        END    FACTOR</lang>

Output:

     1     3     5    15   823  2469  4115 12345

ACL2

<lang Lisp>(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))</lang>

ActionScript

<lang 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; }</lang>

Ada

<lang 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;</lang>

Aikido

<lang 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))</lang>

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. <lang algol68>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 ( #
1. (INT j)VOID:(

      print((sep,whole(j,0))); 
      sep:=", "

OD # ));

 print(new line)

OD</lang>

Output:

        +45: 1, 45, 3, 15, 5, 9
        +53: 1, 53
        +64: 1, 64, 2, 32, 4, 16, 8

ALGOL W

<lang algolw>begin

   % return the factors of n ( n should be >= 1 ) in the array factor       %
   % the bounds of factor should be 0 :: len (len must be at least 1)       %
   % the number of factors will be returned in factor( 0 )                  %
   procedure getFactorsOf ( integer value n
                          ; integer array factor( * )
                          ; integer value len
                          ) ;
   begin
       for i := 0 until len do factor( i ) := 0;
       if n >= 1 and len >= 1 then begin
           integer pos, lastFactor;
           factor( 0 ) := factor( 1 ) := pos := 1;
           % find the factors up to sqrt( n )                               %
           for f := 2 until truncate( sqrt( n ) ) + 1 do begin
               if ( n rem f ) = 0 and pos <= len then begin
                   % found another factor and there's room to store it      %
                   pos           := pos + 1;
                   factor( 0   ) := pos;
                   factor( pos ) := f
               end if_found_factor
           end for_f;
           % find the factors above sqrt( n )                               %
           lastFactor := factor( factor( 0 ) );
           for f := factor( 0 ) step -1 until 1 do begin
               integer newFactor;
               newFactor := n div factor( f );
               if newFactor > lastFactor and pos <= len then begin
                   % found another factor and there's room to store it      %
                   pos           := pos + 1;
                   factor( 0   ) := pos;
                   factor( pos ) := newFactor
               end if_found_factor
           end for_f;
       end if_params_ok
   end getFactorsOf ;

   % prpocedure to test getFactorsOf                                        %
   procedure testFactorsOf( integer value n ) ;
   begin
       integer array factor( 0 :: 100 );
       getFactorsOf( n, factor, 100 );
       i_w := 1; s_w := 0; % set output format                              %
       write( n, " has ", factor( 0 ), " factors:" );
       for f := 1 until factor( 0 ) do writeon( " ", factor( f ) )
   end testFactorsOf ;

   % test the factorising                                                   %
   for i := 1 until 100 do testFactorsOf( i )

end.</lang>

Output:

1 has 1 factors: 1
2 has 2 factors: 1 2
3 has 2 factors: 1 3
4 has 3 factors: 1 2 4
...
96 has 12 factors: 1 2 3 4 6 8 12 16 24 32 48 96
97 has 2 factors: 1 97
98 has 6 factors: 1 2 7 14 49 98
99 has 6 factors: 1 3 9 11 33 99
100 has 9 factors: 1 2 4 5 10 20 25 50 100

APL

<lang APL> factors←{(0=(⍳⍵)|⍵)/⍳⍵}

     factors 12345

1 3 5 15 823 2469 4115 12345

     factors 720

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 36 40 45 48 60 72 80 90 120 144 180 240 360 720</lang>

AutoHotkey

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

}</lang>

Output:

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

AutoIt

<lang AutoIt>;AutoIt Version: 3.2.10.0 $num = 45 MsgBox (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&$intg

EndFunc</lang>

Output:

Factors of 45 are: 1, 3, 5, 9, 15, 45

AWK

syntax: GAWK -f FACTORS_OF_AN_INTEGER.AWK

BEGIN {

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

} </lang>

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). <lang qbasic>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);

NEXT PRINT

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
   NEXT

END SUB</lang>

Output:

 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: <lang dos>@echo off set res=Factors of %1: for /L %%i in (1,1,%1) do call :fac %1 %%i echo %res% goto :eof

fac

set /a test = %1 %% %2 if %test% equ 0 set res=%res% %2</lang>

Output:

>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: <lang dos>@echo off set /p limit=Gimme a number: set res=Factors of %limit%: for /L %%i in (1,1,%limit%) do call :fac %limit% %%i echo %res% goto :eof

fac

set /a test = %1 %% %2 if %test% equ 0 set res=%res% %2</lang>

Output:

>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

BBC BASIC

Works with: BBC BASIC for Windows

<lang bbcbasic> INSTALL @lib$+"SORTLIB"

     sort% = FN_sortinit(0, 0)
     
     PRINT "The factors of 45 are " FNfactorlist(45)
     PRINT "The factors of 12345 are " FNfactorlist(12345)
     END
     
     DEF FNfactorlist(N%)
     LOCAL C%, I%, L%(), L$
     DIM L%(32)
     FOR I% = 1 TO SQR(N%)
       IF (N% MOD I% = 0) THEN
         L%(C%) = I%
         C% += 1
         IF (N% <> I%^2) THEN
           L%(C%) = (N% DIV I%)
           C% += 1
         ENDIF
       ENDIF
     NEXT I%
     CALL sort%, L%(0)
     FOR I% = 0 TO C%-1
       L$ += STR$(L%(I%)) + ", "
     NEXT
     = LEFT$(LEFT$(L$))</lang>

Output:

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

bc

<lang bc>/* 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 = scale
   scale = 0

   /* Two factors are 1 and n (if n != 1) */
   f[l++] = 1
   if (n == 1) return(1)
   h[0] = n

   /* Main loop */
   for (i = 2; i < h[h]; i++) {
       if (n % i == 0) {
           d = n / i
           if (d != i) {
               h[++h] = d
           }
           f[l++] = i
       }
   }

   /* Append the values in h[] to f[] */
   while (h >= 0) {
       f[l++] = h[h--]
   }

   scale = o
   return(l)

}</lang>

Befunge

<lang Befunge>10:p&v: >:0:g%#v_0:g\:0:g/\v

    >:0:g:*`|      >           >0:g1+0:p
            >:0:g:*-#v_0:g\>$>:!#@_.v
                     >     ^ ^  ," "<</lang>

C

<lang c>#include <stdio.h>

include <stdlib.h>

typedef struct {

   int *list;
   short count;

} Factors;

void xferFactors( Factors *fctrs, int *flist, int flix ) {

   int ix, ij;
   int newSize = 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( int num, Factors *fctrs) {

   int flist[301], flix;
   int dvsr;
   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 );

   return fctrs;

}

int main(int argc, char*argv[]) {

   int nums2factor[] = { 2059, 223092870, 3135, 45 };
   Factors ftors = { NULL, 0};
   char sep;
   int i,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");
   }
   return 0;

}</lang>

Prime factoring

<lang C>#include <stdio.h>

include <stdlib.h>
include <string.h>

/* 65536 = 2^16, so we can factor all 32 bit ints */ char bits[65536];

typedef unsigned long ulong; ulong primes[7000], n_primes;

typedef struct { ulong p, e; } prime_factor; /* prime, exponent */

void sieve() { int i, 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; }

int get_prime_factors(ulong n, prime_factor *lst) { ulong i, e, p; int len = 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; } }

return n == 1 ? len : (lst[len].p = n, lst[len].e = 1, ++len); }

int ulong_cmp(const void *a, const void *b) { return *(const ulong*)a < *(const ulong*)b ? -1 : *(const ulong*)a > *(const ulong*)b; }

int get_factors(ulong n, ulong *lst) { int n_f, len, len2, i, j, k, p; prime_factor f[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); return len; }

int main() { ulong fac[10000]; int len, i, j; ulong nums[] = {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"); }

return 0; }</lang>

Output:

3: 1 3
120: 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
1024: 1 2 4 8 16 32 64 128 256 512 1024
3491888400: 1 2 3 4 5 6 7 8 9 10 11 ...(>1900 numbers)... 1163962800 1745944200 3491888400

C++

<lang Cpp>#include <iostream>

include <vector>
include <algorithm>
include <iterator>

std::vector<int> GenerateFactors(int n) {

   std::vector<int> factors;
   factors.push_back(1);
   factors.push_back(n);
   for(int i = 2; i * i <= n; ++i)
   {
       if(n % i == 0)
       {
           factors.push_back(i);
           if(i * i != n)
               factors.push_back(n / i);
       }
   }

   std::sort(factors.begin(), factors.end());
   return factors;

}

int main() {

   const int SampleNumbers[] = {3135, 45, 60, 81};

   for(size_t i = 0; i < sizeof(SampleNumbers) / sizeof(int); ++i)
   {
       std::vector<int> factors = GenerateFactors(SampleNumbers[i]);
       std::cout << "Factors of " << SampleNumbers[i] << " are:\n";
       std::copy(factors.begin(), factors.end(), std::ostream_iterator<int>(std::cout, "\n"));
       std::cout << std::endl;
   }

}</lang>

C#

C# 3.0 <lang csharp>using System; using System.Linq; using System.Collections.Generic;

public static class Extension {

   public static List<int> Factors(this int me)
   {
       return Enumerable.Range(1, me).Where(x => me % x == 0).ToList();
   }

}

class Program {

   static void Main(string[] args)
   {
       Console.WriteLine(String.Join(", ", 45.Factors()));        
   }

}</lang>

C# 1.0 <lang csharp>static void Main(string[] args) { do { Console.WriteLine("Number:"); Int64 p = 0; do { try { p = Convert.ToInt64(Console.ReadLine()); break; } catch (Exception) { }

} while (true);

Console.WriteLine("For 1 through " + ((int)Math.Sqrt(p)).ToString() + ""); for (int x = 1; x <= (int)Math.Sqrt(p); x++) { if (p % x == 0) Console.WriteLine("Found: " + x.ToString() + ". " + p.ToString() + " / " + x.ToString() + " = " + (p / x).ToString()); }

Console.WriteLine("Done."); } while (true); }</lang>

Output:

Number:
32434243
For 1 through 5695
Found: 1. 32434243 / 1 = 32434243
Found: 307. 32434243 / 307 = 105649
Done.

Ceylon

<lang ceylon>shared void run() { {Integer*} getFactors(Integer n) => (1..n).filter((Integer element) => element.divides(n));

for(Integer i in 1..100) { print("the factors of ``i`` are ``getFactors(i)``"); } }</lang>

Chapel

Inspired by the Clojure solution: <lang chapel>iter factors(n) { for i in 1..floor(sqrt(n)):int { if n % i == 0 then { yield i; yield n / i; } } }</lang>

Clojure

<lang lisp>(defn factors [n] (filter #(zero? (rem n %)) (range 1 (inc n))))

(print (factors 45))</lang>

(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. <lang lisp>(defn factors [n]

 (into (sorted-set)
   (mapcat (fn [x] [x (/ n x)])
     (filter #(zero? (rem n %)) (range 1 (inc (Math/sqrt n)))) )))</lang>

Same idea, using for comprehensions. <lang lisp>(defn factors [n]

 (into (sorted-set)
   (reduce concat
     (for [x (range 1 (inc (Math/sqrt n))) :when (zero? (rem n x))]
       [x (/ n x)]))))</lang>

CoffeeScript

<lang coffeescript># 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) ->

 (i for i in [1..n] when n % 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) ->

 for i in [2..n]
   return n if i*i > n
   return i if n % i == 0

prime_factors = (n) ->

 return {} if n == 1
 spf = smallest_prime_factor n
 result = prime_factors(n / spf)
 result[spf] or= 0
 result[spf] += 1
 result

fast_factors = (n) ->

 prime_hash = prime_factors n
 exponents = []
 for p of prime_hash
   exponents.push
     p: p
     exp: 0
 result = []
 while true
   factor = 1
   for obj in exponents
     factor *= Math.pow obj.p, obj.exp
   result.push factor
   break if factor == n
   # roll the odometer
   for obj, i in exponents
     if obj.exp < prime_hash[obj.p]
       obj.exp += 1
       break
     else
       obj.exp = 0
 
 return result.sort (a, b) -> a - b

verify_factors = (factors, n) ->

 expected_result = slow_factors n
 throw Error("wrong length") if factors.length != expected_result.length
 for factor, i in expected_result
   console.log Error("wrong value") if factors[i] != factor

for n in [1, 3, 4, 8, 24, 37, 1001, 11111111111, 99999999999]

 factors = fast_factors n
 console.log n, factors
 if n < 1000000
   verify_factors factors, n</lang>

Output:

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

Common Lisp

We iterate in the range 1..sqrt(n) collecting ‘low’ factors and corresponding ‘high’ factors, and combine at the end to produce an ordered list of factors. <lang lisp>(defun factors (n &aux (lows '()) (highs '()))

 (do ((limit (1+ (isqrt n))) (factor 1 (1+ factor)))
     ((= factor limit)
      (when (= n (* limit limit))
        (push limit highs))
      (remove-duplicates (nreconc lows highs)))
   (multiple-value-bind (quotient remainder) (floor n factor)
     (when (zerop remainder)
       (push factor lows)
       (push quotient highs)))))</lang>

D

Procedural Style

<lang d>import std.stdio, std.math, std.algorithm;

T[] factors(T)(in T n) pure nothrow {

   if (n == 1)
       return [n];

   T[] res = [1, n];
   T limit = cast(T)real(n).sqrt + 1;
   for (T i = 2; i < limit; i++) {
       if (n % i == 0) {
           res ~= i;
           immutable q = n / i;
           if (q > i)
               res ~= q;
       }
   }

   return res.sort().release;

}

void main() {

   writefln("%(%s\n%)", [45, 53, 64, 1111111].map!factors);

}</lang>

Output:

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

Functional Style

<lang d>import std.stdio, std.algorithm, std.range;

auto factors(I)(I n) {

   return iota(1, n + 1).filter!(i => n % i == 0);

}

void main() {

   36.factors.writeln;

}</lang>

Output:

[1, 2, 3, 4, 6, 9, 12, 18, 36]

E

This example is in need of improvement:

Use a cleverer algorithm such as in the Common Lisp example.

<lang e>def factors(x :(int > 0)) {

   var xfactors := []
   for f ? (x % f <=> 0) in 1..x {
     xfactors with= f
   }
   return xfactors

}</lang>

EchoLisp

prime-factors gives the list of n's prime-factors. We mix them to get all the factors. <lang scheme>

ppows input a list g of grouped prime factors ( 3 3 3 ..) returns (1 3 9 27 ...)

(define (ppows g (mult 1)) (for/fold (ppows '(1)) ((a g)) (set! mult (* mult a)) (cons mult ppows)))

factors decomp n into ((2 2 ..) ( 3 3 ..) ) prime factors groups combines (1 2 4 8 ..) (1 3 9 ..) lists

(define (factors n)

  (list-sort <
  (if (<= n 1) '(1) 
       (for/fold (divs'(1)) ((g (map  ppows (group (prime-factors n)))))

(for*/list ((a divs) (b g)) (* a b)))))) </lang>

Output:

<lang scheme> (lib 'bigint) (factors 666)

  → (1 2 3 6 9 18 37 74 111 222 333 666)

(length (factors 108233175859200))

  → 666 ;; 💀

(define huge 1200034005600070000008900000000000000000) (time ( length (factors huge)))

   → (394ms 7776)

</lang>

Ela

Using higher-order function

<lang ela>open list

factors m = filter (\x -> m % x == 0) [1..m]</lang>

Using comprehension

<lang ela>factors m = [x \\ x <- [1..m] | m % x == 0]</lang>

Elixir

<lang elixir>defmodule RC do

 def factor(1), do: [1]
 def factor(n) do
   (for i <- 1..div(n,2), rem(n,i)==0, do: i) ++ [n]
 end

end

Enum.each([45, 53, 64], fn n ->

 IO.puts "#{n}: #{inspect RC.factor(n)}"

end)</lang>

Output:

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

Erlang

with Built in fuctions

<lang erlang>factors(N) ->

   [I || I <- lists:seq(1,trunc(N/2)), N rem I == 0]++[N].</lang>

Recursive

Another, less concise, but faster version <lang erlang>

-module(divs). -export([divs/1]).

divs(0) -> []; divs(1) -> []; divs(N) -> lists:sort(divisors(1,N))++[N].

divisors(1,N) ->

    [1] ++ divisors(2,N,math:sqrt(N)).

divisors(K,_N,Q) when K > Q -> []; divisors(K,N,_Q) when N rem K =/= 0 ->

   [] ++ divisors(K+1,N,math:sqrt(N));

divisors(K,N,_Q) when K * K == N ->

   [K] ++ divisors(K+1,N,math:sqrt(N));

divisors(K,N,_Q) ->

   [K, N div K] ++ divisors(K+1,N,math:sqrt(N)).

</lang>

Output:

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.

ERRE

<lang ERRE> PROGRAM FACTORS

!$DOUBLE

PROCEDURE FACTORLIST(N->L$)

     LOCAL C%,I,FLIPS%,I%
     LOCAL DIM L[32]
     FOR I=1 TO SQR(N) DO
       IF N=I*INT(N/I) THEN
         L[C%]=I
         C%=C%+1
         IF N<>I*I THEN
           L[C%]=INT(N/I)
           C%=C%+1
         END IF
       END IF
     END FOR

     ! BUBBLE SORT ARRAY L[]
     FLIPS%=1
     WHILE FLIPS%>0 DO
        FLIPS%=0
        FOR I%=0 TO C%-2 DO
           IF L[I%]>L[I%+1] THEN SWAP(L[I%],L[I%+1]) FLIPS%=1
        END FOR
     END WHILE

     L$=""
     FOR I%=0 TO C%-1 DO
       L$=L$+STR$(L[I%])+","
     END FOR
     L$=LEFT$(L$,LEN(L$)-1)

END PROCEDURE

BEGIN

   PRINT(CHR$(12);) ! CLS
   FACTORLIST(45->L$)
   PRINT("The factors of 45 are ";L$)
   FACTORLIST(12345->L$)
   PRINT("The factors of 12345 are ";L$)

END PROGRAM </lang>

Output:

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

F#

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. <lang fsharp>let factors number = seq {

   for divisor in 1 .. (float >> sqrt >> int) number do
   if number % divisor = 0 then
       yield divisor
       yield number / divisor

}</lang>

Factor

   USE: math.primes.factors
   ( scratchpad ) 24 divisors .
   { 1 2 3 4 6 8 12 24 }

FALSE

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. <lang Forth>: 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 .factors 53 .factors 64 .factors 100 .factors</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>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</lang>

Frink

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.

The factors[n] function will return the prime decomposition of n.

The allFactors[n, include1=true, includeN=true, sort=true, onlyToSqrt=false] function will return all factors of n. The optional arguments include1 and includeN indicate if the numbers 1 and n are to be included in the results. If the optional argument sort is true, the results will be sorted. If the optional argument onlyToSqrt=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:

<lang frink>allFactors[n]</lang>

FunL

Function to compute set of factors: <lang funl>def factors( n ) = {d | d <- 1..n if d|n}</lang>

Test: <lang funl>for x <- [103, 316, 519, 639, 760]

 println( 'The set of factors of ' + x + ' is ' + factors(x) )</lang>

Output:

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}

GAP

<lang gap># Built-in function DivisorsInt(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 n

div := 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 ]</lang>

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. <lang go>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))

}</lang>

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: <lang groovy>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]

}</lang>

Test: <lang groovy>((1..30) + [333333]).each { println ([number:it, factors:factorize(it)]) }</lang>

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

Haskell

Using D. Amos module Primes [1] for finding prime factors <lang Haskell>import HFM.Primes(primePowerFactors) import Data.List

factors = map product.

         mapM (uncurry((. enumFromTo 0) . map .(^) )) . primePowerFactors</lang>

List comprehension

Naive, functional, no import <lang Haskell>factors_naive n = [i | i <-[1..n], (mod n i) == 0]</lang> <lang Haskell>factors_naive 6 [1,2,3,6] </lang>

Factor, cofactor. Rearrange a list of tuples to a sorted list <lang Haskell>import Data.List tuple_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]] ))

</lang> <lang Haskell>factors_co 6 [1,2,3,6] </lang>

A cleaner, simplified version of the code above, without the sorting nor the tuples, increasing speed and making it possible to see results in real time (if using GHCi) <lang Haskell>import Data.List factors n = lows ++ (reverse $ map (div n) lows)

   where lows = filter ((== 0) . mod n) [1..truncate . sqrt $ fromIntegral n]

</lang> <lang Haskell>*Main> :set +s

Main> factors 120

[1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120] (0.01 secs, 7578656 bytes)</lang>

HicEst

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

Icon and Unicon

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

link factors</lang>

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

Library: Icon Programming Library

divisors

J

J has a primitive, q: which returns its argument's prime factors. <lang J>q: 40

2 2 2 5</lang>

Alternatively, q: can produce provide a table of the exponents of the unique relevant prime factors <lang J> __ q: 420 2 3 5 7 2 1 1 1</lang>

With this, we can form lists of each of the potential relevant powers of each of these prime factors <lang J> (^ i.@>:)&.>/ __ q: 420 ┌─────┬───┬───┬───┐ │1 2 4│1 3│1 5│1 7│ └─────┴───┴───┴───┘</lang>

From here, it's a simple matter (*/&>@{) to compute all possible factors of the original number <lang J>factrs=: */&>@{@((^ i.@>:)&.>/)@q:~&__

  factrs 40
1  5
2 10
4 20
8 40</lang>

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:

<lang J> factors=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__

  factors 420

1 2 3 4 5 6 7 10 12 14 15 20 21 28 30 35 42 60 70 84 105 140 210 420</lang>

A less efficient, but concise variation on this theme:

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: <lang J>factorsOfNumber=: monad define

 Y=. y"_
 /:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y

)

  factorsOfNumber 40

1 2 4 5 8 10 20 40</lang>

Another approach:

<lang J>odometer =: #: i.@(*/) factors=: (*/@:^"1 odometer@:>:)/@q:~&__</lang>

See http://www.jsoftware.com/jwiki/Essays/Odometer

Java

Works with: Java version 5+

<lang java5>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;

}</lang>

JavaScript

Imperative

<lang 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]</lang>

Functional (ES 5)

Translating the naive list comprehension example from Haskell, using a list monad for the comprehension

<lang JavaScript>// Monadic bind (chain) for lists function chain(xs, f) {

 return [].concat.apply([], xs.map(f));

}

// [m..n] function range(m, n) {

 return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
   return m + i;
 });

}

function factors_naive(n) {

 return chain( range(1, n), function (x) {       // monadic chain/bind
   return n % x ? [] : [x];                      // monadic fail or inject/return
 });

}

factors_naive(6)</lang>

Output: <lang JavaScript>[1, 2, 3, 6]</lang>

Translating the Haskell (lows and highs) example

<lang JavaScript>console.log(

 (function (lstTest) {

   // INTEGER FACTORS
   function integerFactors(n) {
     var rRoot = Math.sqrt(n),
       intRoot = Math.floor(rRoot),

       lows = range(1, intRoot).filter(function (x) {
         return (n % x) === 0;
       });

     // for perfect squares, we can drop the head of the 'highs' list
     return lows.concat(lows.map(function (x) {
       return n / x;
     }).reverse().slice((rRoot === intRoot) | 0));
   }

   // [m .. n]
   function range(m, n) {
     return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
       return m + i;
     });
   }

   /*************************** TESTING *****************************/

   // TABULATION OF RESULTS IN SPACED AND ALIGNED COLUMNS
   function alignedTable(lstRows, lngPad, fnAligned) {
     var lstColWidths = range(0, lstRows.reduce(function (a, x) {
       return x.length > a ? x.length : a;
     }, 0) - 1).map(function (iCol) {
       return lstRows.reduce(function (a, lst) {
         var w = lst[iCol] ? lst[iCol].toString().length : 0;
         return (w > a) ? w : a;
       }, 0);
     });

     return lstRows.map(function (lstRow) {
       return lstRow.map(function (v, i) {
         return fnAligned(v, lstColWidths[i] + lngPad);
       }).join()
     }).join('\n');
   }

   function alignRight(n, lngWidth) {
     var s = n.toString();
     return Array(lngWidth - s.length + 1).join(' ') + s;
   }

   // TEST
   return '\nintegerFactors(n)\n\n' + alignedTable(
     lstTest.map(integerFactors).map(function (x, i) {
       return [lstTest[i], '-->'].concat(x);
     }), 2, alignRight
   ) + '\n';

 })([25, 45, 53, 64, 100, 102, 120, 12345, 32766, 32767])

);</lang>

Output:

<lang JavaScript>integerFactors(n)

    25  -->  1   5  25
    45  -->  1   3   5    9   15    45
    53  -->  1  53
    64  -->  1   2   4    8   16    32    64
   100  -->  1   2   4    5   10    20    25     50  100
   102  -->  1   2   3    6   17    34    51    102
   120  -->  1   2   3    4    5     6     8     10   12   15   20   24    30     40     60    120
 12345  -->  1   3   5   15  823  2469  4115  12345
 32766  -->  1   2   3    6   43    86   127    129  254  258  381  762  5461  10922  16383  32766
 32767  -->  1   7  31  151  217  1057  4681  32767

</lang>

jq

Works with: jq version 1.4

<lang jq># This implementation uses "sort" for tidiness def 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</lang>

Output:

$ jq -n -M -r -c -f factors.jq
45: [1,3,5,9,15,45]
53: [1,53]
64: [1,2,4,8,16,32,64]

Julia

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

Output:

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

K

<lang K> f:{d:&~x!'!1+_sqrt x;?d,_ x%|d}

f 1

1

f 3

1 3

  f 120

1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120

  f 1024

1 2 4 8 16 32 64 128 256 512 1024

  f 600851475143

1 71 839 1471 6857 59569 104441 486847 1234169 5753023 10086647 87625999 408464633 716151937 8462696833 600851475143

  #f 3491888400 / has 1920 factors

1920

  / Number of factors for 3491888400 .. 3491888409
  #:'f' 3491888400+!10

1920 16 4 4 12 16 32 16 8 24</lang>

LFE

Using List Comprehensions

This following function is elegant looking and concise. However, it will not handle large numbers well: it will consume a great deal of memory (on one large number, the function consumed 4.3GB of memory on my desktop machine): <lang lisp> (defun factors (n)

 (list-comp
   ((<- i (when (== 0 (rem n i))) (lists:seq 1 (trunc (/ n 2)))))
   i))

</lang>

Non-Stack-Consuming

This version will not consume the stack (this function only used 18MB of memory on my machine with a ridiculously large number): <lang lisp> (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)))

</lang>

Output:

> (factors 10677106534462215678539721403561279)
(104729 104729 104729 98731 98731 32579 29269 1)

Liberty BASIC

<lang lb>num = 10677106534462215678539721403561279 maxnFactors = 1000 dim primeFactors(maxnFactors), nPrimeFactors(maxnFactors) global nDifferentPrimeNumbersFound, nFactors, iFactor

print "Start finding all factors of ";num; ":"

nDifferentPrimeNumbersFound=0 dummy = factorize(num,2) nFactors = showPrimeFactors(num) dim factors(nFactors) dummy = generateFactors(1,1) sort factors(), 0, nFactors-1 for i=1 to nFactors

  print i;"     ";factors(i-1)

next i

print "done"

wait

function factorize(iNum,offset)

   factorFound=0
   i = offset
   do
       if (iNum MOD i)=0 _
       then
           if primeFactors(nDifferentPrimeNumbersFound) = i _
           then
              nPrimeFactors(nDifferentPrimeNumbersFound) = nPrimeFactors(nDifferentPrimeNumbersFound) + 1
           else
              nDifferentPrimeNumbersFound = nDifferentPrimeNumbersFound + 1
              primeFactors(nDifferentPrimeNumbersFound) = i
              nPrimeFactors(nDifferentPrimeNumbersFound) = 1
           end if
           if iNum/i<>1 then dummy = factorize(iNum/i,i)
           factorFound=1
        end if
        i=i+1
   loop while factorFound=0 and i<=sqr(iNum)
   if factorFound=0 _
   then
      nDifferentPrimeNumbersFound = nDifferentPrimeNumbersFound + 1
      primeFactors(nDifferentPrimeNumbersFound) = iNum
      nPrimeFactors(nDifferentPrimeNumbersFound) = 1
   end if

end function

function showPrimeFactors(iNum)

  showPrimeFactors=1
  print iNum;" = ";
  for i=1 to nDifferentPrimeNumbersFound
     print primeFactors(i);"^";nPrimeFactors(i);
     if i<nDifferentPrimeNumbersFound then print " * "; else print ""
     showPrimeFactors = showPrimeFactors*(nPrimeFactors(i)+1)
  next i
  end function

function generateFactors(product,pIndex)

  if pIndex>nDifferentPrimeNumbersFound _
  then
     factors(iFactor) = product
     iFactor=iFactor+1
  else
     for i=0 to nPrimeFactors(pIndex)
        dummy = generateFactors(product*primeFactors(pIndex)^i,pIndex+1)
     next i
  end if
  end function</lang>

Output:

<lang lb>Start finding all factors of 10677106534462215678539721403561279: 10677106534462215678539721403561279 = 29269^1 * 32579^1 * 98731^2 * 104729^3 1 1 2 29269 3 32579 4 98731 5 104729 6 953554751 7 2889757639 8 3065313101 9 3216557249 10 3411966091 11 9747810361 12 10339998899 13 10968163441 14 94145414120981 15 99864835517479 16 285308661456109 17 302641427774831 18 317573913751019 19 321027175754629 20 336866824130521 21 357331796744339 22 1020878431297169 23 1082897744693371 24 1148684789012489 25 9295070881578575111 26 9859755075476219149 27 10458744358910058191 28 29880090805636839461 29 31695334089430275799 30 33259198413230468851 31 33620855089606540541 32 35279725624365333809 33 37423001741237879131 34 106915577231321212201 35 113410797903992051459 36 973463478356842592799919 37 1032602289299548955255621 38 1095333837964291484285239 39 3129312029983540559911069 40 3319420643851943354153471 41 3483202590619213772296379 42 3694810384914157044482761 43 11197161487859039232598529 44 101949856624833767901342716951 45 108143405156052462534965931709 46 327729719588146219298926345301 47 364792324112959639158827476291 48 10677106534462215678539721403561279 done</lang>

Logo

<lang logo>to factors :n

 output filter [equal? 0 modulo :n ?] iseq 1 :n

end

show factors 28 ; [1 2 4 7 14 28]</lang>

Lua

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

end</lang>

Maple

<lang Maple> numtheory:-divisors(n); </lang>

Mathematica / Wolfram Language

<lang Mathematica>Factorize[n_Integer] := Divisors[n]</lang>

MATLAB / Octave

<lang Matlab> 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;
</lang>

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. <lang maxima>(%i96) divisors(100); (%o96) {1,2,4,5,10,20,25,50,100}</lang>

Such a function could be implemented like so: <lang maxima>divisors2(n) := map( lambda([l], lreduce("*", l)),

   apply( cartesian_product,
   map( lambda([fac],
       setify(makelist(fac[1]^i, i, 0, fac[2]))),
   ifactors(n))));</lang>

MAXScript

<lang MAXScript> fn factors n = ( return (for i = 1 to n+1 where mod n i == 0 collect i) ) </lang>

Output:

<lang MAXScript> 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)

</lang>

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:

The input number itself and 1 are both considered factors.
The numbers between 2 and the square root of the input number are checked for even division.
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

<lang Mercury>:- 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.</lang>

Use and output

Use of the code looks like this:

$ mmc fac.m && ./fac 100 999 12345678 booger
factor(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])

МК-61/52

П9	1	П6	КИП6	ИП9	ИП6	/	П8	^	[x]
x#0	21	-	x=0	03	ИП6	С/П	ИП8	П9	БП
04	1	С/П	БП	21

MUMPS

<lang MUMPS>factors(num) New fctr,list,sep,sqrt If num<1 Quit "Too small a number" If num["." Quit "Not an integer" Set sqrt=num**0.5\1 For fctr=1:1:sqrt Set:num/fctr'["." list(fctr)=1,list(num/fctr)=1 Set (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]</lang>

NetRexx

Translation of: REXX

<lang NetRexx>/* NetRexx ***********************************************************

21.04.2013 Walter Pachl
21.04.2013 add method main to accept argument(s)
- - - - /

options replace format comments java crossref symbols nobinary class 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           */</lang>

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

Nim

<lang nim>import intsets, math, algorithm

proc factors(n): seq[int] =

 var fs = initIntSet()
 for x in 1 .. int(sqrt(float(n))):
   if n mod x == 0:
     fs.incl(x)
     fs.incl(n div x)

 result = @[]
 for x in fs:
   result.add(x)
 sort(result, system.cmp[int])

echo factors(45)</lang>

Niue

<lang 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 ) newline 53 factors .s .clr ( => 1 53 ) newline 64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline 12 factors .s .clr ( => 1 2 3 4 6 12 ) </lang>

Oberon-2

Oxford Oberon-2 <lang oberon2> 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 v END 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.Ln END Factors. </lang>

Output:

Objeck

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

}</lang>

OCaml

<lang ocaml>let rec range = function 0 -> [] | n -> range(n-1) @ [n]

let factors n =

 List.filter (fun v -> (n mod v) = 0) (range n)</lang>

Oforth

<lang Oforth>Integer method: factors { self seq filter(#[ self isMultiple ]) }

120 factors println</lang>

Output:

[1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]

Oz

<lang 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.'<'}
 end

in

 {Show {Factors 53}}</lang>

PARI/GP

<lang parigp>divisors(n)</lang>

Panda

Panda has a factor function already, it's defined as: <lang panda>fun factor(n) type integer->integer

  f where n.mod(1..n=>f)==0

45.factor</lang>

Pascal

Translation of: Fortran

Works with: Free Pascal version 2.6.2

<lang pascal>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.</lang>

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

small improvement

the factors are in ascending order.

Works with: Free Pascal

<lang pascal>program factors; {Looking for extreme composite numbers: http://wwwhomes.uni-bielefeld.de/achim/highly.txt}

const

 MAXFACTORCNT = 1920; //number := 3491888400;

var

 FaktorList : array[0..MAXFACTORCNT] of LongWord;
 i, number,quot,cnt: LongWord;

begin

 writeln('Enter a number between 1 and 4294967295: ');
 write('3491888400 is a nice choice ');
 readln(number);

 cnt := 0;
 i := 1;
 repeat
   quot := number div i;
   if quot *i-number = 0 then
   begin
     FaktorList[cnt] := i;
     FaktorList[MAXFACTORCNT-cnt] := quot;
     inc(cnt);
   end;
   inc(i);
 until i> quot;
 writeln(number,' has ',2*cnt,' factors');
 dec(cnt);
 For i := 0 to cnt do
   write(FaktorList[i],' ,');
 For i := cnt downto 1 do
   write(FaktorList[MAXFACTORCNT-i],' ,');

{ the last without ','}

 writeln(FaktorList[MAXFACTORCNT]);

end.</lang>

Output:

Enter a number between 1 and 4294967295: 
3491888400 is a nice choice 120
120 has 16 factors
1 ,2 ,3 ,4 ,5 ,6 ,8 ,10 ,12 ,15 ,20 ,24 ,30 ,40 ,60 ,120

Perl

<lang perl>sub factors {

       my($n) = @_;
       return grep { $n % $_ == 0 }(1 .. $n);

} print join ' ',factors(64), "\n";</lang>

Or more intelligently:

<lang perl>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";</lang>

One could also use a module, e.g.:

Library: ntheory

<lang perl>use ntheory qw/divisors/; print join " ", divisors(12345678), "\n";

Alternately something like: fordivisors { say } 12345678; </lang>

Perl 6

Works with: Rakudo version 2015.12

<lang perl6>sub factors (Int $n) { squish sort ($_, $n div $_ if $n %% $_ for 1 .. sqrt $n) }</lang>

Phix

There is a builtin factors(n), which takes an optional second parameter to include 1 and n, so eg ?factors(12345,1) displays

Output:

{1,3,5,15,823,2469,4115,12345}

You can find the implementation of factors() and prime_factors() in builtins\pfactors.e

PHP

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

}</lang>

PicoLisp

<lang PicoLisp>(de factors (N)

  (filter
     '((D) (=0 (% N D)))
     (range 1 N) ) )</lang>

PL/I

<lang PL/I>do i = 1 to n;

  if mod(n, i) = 0 then put skip list (i);

end;</lang>

PowerShell

Straightforward but slow

<lang powershell>function Get-Factor ($a) {

   1..$a | Where-Object { $a % $_ -eq 0 }

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

<lang powershell>function Get-Factor ($a) {

   1..[Math]::Sqrt($a) `
       | Where-Object { $a % $_ -eq 0 } `
       | ForEach-Object { $_; $a / $_ } `
       | Sort-Object -Unique

}</lang> 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: <lang ProDOS>editvar /newvar /value=a /userinput=1 /title=Enter an integer: do /delimspaces %% -a- >b printline Factors of -a-: -b- </lang>

Prolog

Simple Brute Force Implementation <lang Prolog> brute_force_factors( N , Fs ) :-

 integer(N) ,
 N > 0 ,  
 setof( F , ( between(1,N,F) , N mod F =:= 0 ) , Fs )
 .

</lang>

A Slightly Smarter Implementation <lang Prolog> 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 )
 .

</lang>

Not every Prolog has between/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)
 .

</lang>

Output:

?- 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] .

PureBasic

<lang PureBasic>Procedure PrintFactors(n)

 Protected i, lim=Round(sqr(n),#PB_Round_Up)
 NewList F.i()
 For i=1 To lim
   If n%i=0
     AddElement(F()): F()=i
     AddElement(F()): F()=n/i
   EndIf
 Next
 ;- Present the result
 SortList(F(),#PB_Sort_Ascending)
 ForEach F()
   Print(str(F())+" ")
 Next

EndProcedure

If OpenConsole()

 Print("Enter integer to factorize: ")
 PrintFactors(Val(Input()))
 Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input()

EndIf</lang>

Output:

 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): <lang python>>>> def factors(n):

     return [i for i in range(1, n + 1) if not n%i]</lang>

Slightly better (realize that there are no factors between n/2 and n): <lang python>>>> 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]</lang>

Much better (realize that factors come in pairs, the smaller of which is no bigger than sqrt(n)): <lang python>>>> 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]</lang>

More efficient when factoring many numbers: <lang python>from itertools import chain, cycle, accumulate # last of which is Python 3 only

def 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</lang>

R

<lang 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)</lang>

1  2  3  4  5  6 10 12 15 20 30 60

<lang R>factors(c(45, 53, 64))</lang>

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

</lang>

REALbasic

<lang vb>Function factors(num As UInt64) As UInt64()

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

End Function</lang>

REXX

optimized version

This REXX version has no effective limits on the number of decimal digits in the number to be factored [by adjusting the number of digits (precision)].
This REXX version also supports negative integers and zero.
It also indicates primes in the output as well as the number of factors. <lang rexx>/*REXX program displays divisors of any [negative/zero/positive] integer(s).*/ parse arg bot top inc . /*optional args.*/ top=word(top bot 20,1); bot=word(bot 1,1); inc=word(inc 1,1) /*range options.*/ w=length(high)+1; numeric digits max(9,w); $='∞' /*digits for // */ @.=left(,7); @.1='{unity}'; @.2='[prime]'; @.$=' {'$"} " /*some literals.*/ say center('n',1+w) '#divisors' center('divisors',60) /*show a header.*/ say copies('═',1+w) '═════════' copies('═' ,60) /* " " sep. */

    do n=bot  to top  by inc;   divs=divisors(n);    #=words(divs)
    if divs==$  then do;  #=$;  divs='  (infinite)'; end    /*handle infinity*/
    p=@.#;           if n<0  then p=@..                     /*handle negative*/
    say center(n,w+1)    center('['#"]",9)     "──► "       p      ' '     divs
    end   /*n*/                       /* [↑]   process a range of integers.  */

exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ divisors: procedure; parse arg x; x=abs(x); if x==1 then return 1 odd=x//2; b=x; if x==0 then return '∞' a=1 /* [↓] process only EVEN│ODD integers.*/

  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 factors to α&ß lists.*/
  end   /*j*/                         /* [↑]  %   is REXX's integer division.*/
                                      /* [↓]  adjust for a square.       ___ */

if j*j==x then return a j b /*Was X a square? If so, insert √ x */

                return  a   b         /*return the divisors of both lists.   */</lang>

output when the input used is: -6 200

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

Alternate Version

<lang REXX>/* 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
 End

do j=low to high

 say '   n = ' right(j,6) "   divisors = " divs(j)
 end

exit

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           */</lang>

Ruby

<lang ruby>class Integer

 def factors() (1..self).select { |n| (self % n).zero? } end

end p 45.factors</lang>

[1, 3, 5, 9, 15, 45]

As we only have to loop up to ${\sqrt {n}}$ , we can write <lang ruby>class Integer

 def factors
   1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i| 
     f << self/i unless i == self/i
     f << i
   end.sort
 end

end [45, 53, 64].each {|n| puts "#{n} : #{n.factors}"}</lang>

Output:

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

Run BASIC

<lang runbasic>PRINT "Factors of 45 are ";factorlist$(45) PRINT "Factors of 12345 are "; factorlist$(12345) END

function factorlist$(f) DIM L(100) FOR i = 1 TO SQR(f)

 IF (f MOD i) = 0 THEN
   L(c) = i
   c = c + 1
   IF (f <> i^2) THEN
     L(c) = (f / i)
     c = c + 1
   END IF
 END IF

NEXT i s = 1 while s = 1 s = 0 for i = 0 to c-1

if L(i) > L(i+1) and L(i+1) <> 0 then
 t = L(i)
 L(i) = L(i+1)
 L(i+1) = t
 s      = 1
end if

next i wend FOR i = 0 TO c-1

 factorlist$ = factorlist$ + STR$(L(i)) + ", "

NEXT end function</lang>

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

<lang sather>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;</lang>

Scala

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

Scheme

This implementation uses a naive trial division algorithm. <lang scheme>(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)</lang>

Output:

 (1 239 4649 1111111)

Seed7

<lang seed7>$ 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;</lang>

Output:

Factors of 45: 1, 45, 3, 15, 5, 9
Factors of 53: 1, 53
Factors of 64: 1, 64, 2, 32, 4, 16, 8

SequenceL

Brute Force Method

A simple brute force method using an indexed partial function as a filter. <lang sequencel>Factors(num(0))[i] := i when num mod i = 0 foreach i within 1 ... num;</lang>

Slightly More Efficient Method

A slightly more efficient method, only going up to the sqrt(n). <lang sequencel>Factors(num(0)) := let factorPairs[i] := [i] when i = sqrt(num) else [i, num/i] when num mod i = 0 foreach i within 1 ... floor(sqrt(num)); in join(factorPairs);</lang>

Sidef

<lang ruby>func factors(n) {

 var divs = []
 range(1, n.sqrt.int).each { |d|
   divs << d if n%%d
 }
 divs + [divs[-1]**2 == n ? divs.pop : ()] + divs.reverse.map{|d| n/d }

}

[53, 64, 32766].each { |n|

   say "factors(#{n}): #{factors(n)}"

}</lang>

Output:

factors(53): 1 53
factors(64): 1 2 4 8 16 32 64
factors(32766): 1 2 3 6 43 86 127 129 254 258 381 762 5461 10922 16383 32766

Slate

<lang slate>n@(Integer traits) primeFactors [

 [| :result |
  result nextPut: 1.
  n primesDo: [| :prime | result nextPut: prime]] writingAs: {}

].</lang> where primesDo: is a part of the standard numerics library: <lang slate>n@(Integer traits) primesDo: block "Decomposes the Integer into primes, applying the block to each (in increasing order)." [| 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."

].</lang>

Smalltalk

Copied from the Python example, but code added to the Integer built in class:

<lang smalltalk>Integer>>factors | a | a := OrderedCollection new. 1 to: (self / 2) do: [ :i | ((self \\ i) = 0) ifTrue: [ a add: i ] ]. a add: self. ^a</lang>

Then use as follows:

<lang smalltalk> 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) </lang>

Swift

Simple implementation: <lang Swift>func factors(n: Int) -> [Int] {

   return filter(1...n) { n % $0 == 0 }

}</lang> More efficient implementation: <lang Swift>import func Darwin.sqrt

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

}</lang> Call: <lang Swift>println(factors(4)) println(factors(1)) println(factors(25)) println(factors(63)) println(factors(19)) println(factors(768))</lang>

Output:

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

Tcl

<lang tcl>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]</lang>

Output:

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

UNIX Shell

This should work in all Bourne-compatible shells, assuming the system has both sort and at least one of bc or dc.

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

} </lang>

Ursala

The simple way: <lang Ursala>#import std

import nat

factors "n" = (filter not remainder/"n") nrange(1,"n")</lang> The complicated way: <lang Ursala>factors "n" = nleq-<&@s <.~&r,quotient>*= "n"-* (not remainder/"n")*~ nrange(1,root("n",2))</lang> 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 <lang Ursala>factors = nleq-<&@rrZPFLs+ ^(~&r,division)^*D/~& nrange/1+ &!*K31</lang> where nleq-<& isn't strictly necessary unless an ordered list is required. <lang Ursala>#cast %nL

example = factors 100</lang>

Output:

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

VBA

<lang VBA>Function Factors(x As Integer) As String

Application.Volatile
Dim i As Integer
Dim cooresponding_factors As String
Factors = 1
corresponding_factors = x
For i = 2 To Sqr(x)
 If x Mod i = 0 Then
  Factors = Factors & ", " & i
  If i <> x / i Then corresponding_factors = x / i & ", " & corresponding_factors
 End If
Next i
If x <> 1 Then Factors = Factors & ", " & corresponding_factors

End Function</lang>

Output:

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"

Wortel

<lang wortel>@let {

 factors1      &n !-\%%n @to n
 factors_tacit @(\\%% !- @to)
 [[
   !factors1 10 
   !factors_tacit 100 
   !factors1 720 
 ]]

}</lang>

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

XPL0

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

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

zkl

Translation of: Chapel

<lang zkl>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 comprehension</lang>

Output:

zkl: 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))

@@ Line 2,390: / Line 2,390: @@
 =={{header|Perl 6}}==
+{{works with|Rakudo|2015.12}}
 <lang perl6>sub factors (Int $n) { squish sort ($_, $n div $_ if $n %% $_ for 1 .. sqrt $n) }</lang>