# 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  ## 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 ## BBC BASIC  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$))

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

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

### Prime factoring

#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;}
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++

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

## C#

C# 3.0

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

C# 1.0

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

Example output:

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

## Clojure

(defn factors [n] 	(filter #(zero? (rem n %)) (range 1 (inc n)))) (print (factors 45))
(1 3 5 9 15 45)


Improved version. Considers small factors from 1 up to (sqrt n) -- we increment it because range does not include the end point. Pair each small factor with its co-factor, flattening the results, and put them into a sorted set to get the factors in order.

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

Same idea, using for comprehensions.

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

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

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.

(defun factors (n &aux (lows '()) (highs '()))  (do ((limit (isqrt n)) (factor 1 (1+ factor)))      ((= factor limit)       (when (= n (* limit limit))         (push limit highs))       (nreconc lows highs))    (multiple-value-bind (quotient remainder) (floor n factor)      (when (zerop remainder)        (push factor lows)        (push quotient highs)))))

## D

### Procedural Style

import std.stdio, std.math, std.algorithm; T[] factor(T)(in T n) /*pure nothrow*/ {    if (n == 1) return [n];     T[] res = [1, n];    T limit = cast(T)sqrt(cast(real)n) + 1;    for (T i = 2; i < limit; i++) {        if (n % i == 0) {            res ~= i;            auto q = n / i;            if (q > i)                res ~= q;        }    }     return res.sort().release();} void main() {    foreach (i; [45, 53, 64, 1111111])        writeln(factor(i));}
Output:
[1, 3, 5, 9, 15, 45]
[1, 53]
[1, 2, 4, 8, 16, 32, 64]
[1, 239, 4649, 1111111]

### Functional Style

import std.stdio, std.algorithm, std.range; auto factors(I)(I n) {    return iota(1, n+1).filter!(i => n % i == 0)();} void main() {    writeln(factors(36));}
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.
def factors(x :(int > 0)) {    var xfactors := []    for f ? (x % f <=> 0) in 1..x {      xfactors with= f    }    return xfactors}

## Ela

### Using higher-order function

open list factors m = filter (\x -> m % x == 0) [1..m]

### Using comprehension

factors m = [x \\ x <- [1..m] | m % x == 0]

## Erlang

factors(N) ->    [I || I <- lists:seq(1,trunc(math:sqrt(N))), N rem I == 0]++[N].

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

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

## Factor

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


## FALSE

[1[\$@$@-][\$@$@$@$@\/*=[$." "]?1+]#.%]f:45f;! 53f;! 64f;! ## 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]] ## Haskell 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 ## 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] ## 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: $ 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


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

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 /*REXX program to calculate and show divisors of positive integer(s). */parse arg low high .; high=word(high low 20,1); low=word(low 1,1)numeric digits max(9,length(high)) /*ensure modulus has enough digs.*/ do n=low to high /*the default range is: 1 ──> 20*/ say 'divisors of' right(n,length(high)) " ──► " divisors(n) 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; a=1; odd=x//2 /*Odd? Then use only odd divisors*/ do j=2+odd by 1+odd while j*j<x /*divide by all integers up to √x*/ if x//j\==0 then iterate /*¬ divisible? Then keep looking*/ a=a j; b=x%j b /*add a divisor to both lists. */ end /*j*/ if j*j==x then b=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 divisors of 1 ──► 1 divisors of 2 ──► 1 2 divisors of 3 ──► 1 3 divisors of 4 ──► 1 2 4 divisors of 5 ──► 1 5 divisors of 6 ──► 1 2 3 6 divisors of 7 ──► 1 7 divisors of 8 ──► 1 2 4 8 divisors of 9 ──► 1 3 9 divisors of 10 ──► 1 2 5 10 divisors of 11 ──► 1 11 divisors of 12 ──► 1 2 3 4 6 12 divisors of 13 ──► 1 13 divisors of 14 ──► 1 2 7 14 divisors of 15 ──► 1 3 5 15 divisors of 16 ──► 1 2 4 8 16 divisors of 17 ──► 1 17 divisors of 18 ──► 1 2 3 6 9 18 divisors of 19 ──► 1 19 divisors of 20 ──► 1 2 4 5 10 20 divisors of 21 ──► 1 3 7 21 divisors of 22 ──► 1 2 11 22 divisors of 23 ──► 1 23 divisors of 24 ──► 1 2 3 4 6 8 12 24 divisors of 25 ──► 1 5 25 divisors of 26 ──► 1 2 13 26 divisors of 27 ──► 1 3 9 27 divisors of 28 ──► 1 2 4 7 14 28 divisors of 29 ──► 1 29 divisors of 30 ──► 1 2 3 5 6 10 15 30 divisors of 31 ──► 1 31 divisors of 32 ──► 1 2 4 8 16 32 divisors of 33 ──► 1 3 11 33 divisors of 34 ──► 1 2 17 34 divisors of 35 ──► 1 5 7 35 divisors of 36 ──► 1 2 3 4 6 9 12 18 36 divisors of 37 ──► 1 37 divisors of 38 ──► 1 2 19 38 divisors of 39 ──► 1 3 13 39 divisors of 40 ──► 1 2 4 5 8 10 20 40 divisors of 41 ──► 1 41 divisors of 42 ──► 1 2 3 6 7 14 21 42 divisors of 43 ──► 1 43 divisors of 44 ──► 1 2 4 11 22 44 divisors of 45 ──► 1 3 5 9 15 45 divisors of 46 ──► 1 2 23 46 divisors of 47 ──► 1 47 divisors of 48 ──► 1 2 3 4 6 8 12 16 24 48 divisors of 49 ──► 1 7 49 divisors of 50 ──► 1 2 5 10 25 50 divisors of 51 ──► 1 3 17 51 divisors of 52 ──► 1 2 4 13 26 52 divisors of 53 ──► 1 53 divisors of 54 ──► 1 2 3 6 9 18 27 54 divisors of 55 ──► 1 5 11 55 divisors of 56 ──► 1 2 4 7 8 14 28 56 divisors of 57 ──► 1 3 19 57 divisors of 58 ──► 1 2 29 58 divisors of 59 ──► 1 59 divisors of 60 ──► 1 2 3 4 5 6 10 12 15 20 30 60 divisors of 61 ──► 1 61 divisors of 62 ──► 1 2 31 62 divisors of 63 ──► 1 3 7 9 21 63 divisors of 64 ──► 1 2 4 8 16 32 64 divisors of 65 ──► 1 5 13 65 divisors of 66 ──► 1 2 3 6 11 22 33 66 divisors of 67 ──► 1 67 divisors of 68 ──► 1 2 4 17 34 68 divisors of 69 ──► 1 3 23 69 divisors of 70 ──► 1 2 5 7 10 14 35 70 divisors of 71 ──► 1 71 divisors of 72 ──► 1 2 3 4 6 8 9 12 18 24 36 72 divisors of 73 ──► 1 73 divisors of 74 ──► 1 2 37 74 divisors of 75 ──► 1 3 5 15 25 75 divisors of 76 ──► 1 2 4 19 38 76 divisors of 77 ──► 1 7 11 77 divisors of 78 ──► 1 2 3 6 13 26 39 78 divisors of 79 ──► 1 79 divisors of 80 ──► 1 2 4 5 8 10 16 20 40 80 divisors of 81 ──► 1 3 9 27 81 divisors of 82 ──► 1 2 41 82 divisors of 83 ──► 1 83 divisors of 84 ──► 1 2 3 4 6 7 12 14 21 28 42 84 divisors of 85 ──► 1 5 17 85 divisors of 86 ──► 1 2 43 86 divisors of 87 ──► 1 3 29 87 divisors of 88 ──► 1 2 4 8 11 22 44 88 divisors of 89 ──► 1 89 divisors of 90 ──► 1 2 3 5 6 9 10 15 18 30 45 90 divisors of 91 ──► 1 7 13 91 divisors of 92 ──► 1 2 4 23 46 92 divisors of 93 ──► 1 3 31 93 divisors of 94 ──► 1 2 47 94 divisors of 95 ──► 1 5 19 95 divisors of 96 ──► 1 2 3 4 6 8 12 16 24 32 48 96 divisors of 97 ──► 1 97 divisors of 98 ──► 1 2 7 14 49 98 divisors of 99 ──► 1 3 9 11 33 99 divisors of 100 ──► 1 2 4 5 10 20 25 50 100 divisors of 101 ──► 1 101 divisors of 102 ──► 1 2 3 6 17 34 51 102 divisors of 103 ──► 1 103 divisors of 104 ──► 1 2 4 8 13 26 52 104 divisors of 105 ──► 1 3 5 7 15 21 35 105 divisors of 106 ──► 1 2 53 106 divisors of 107 ──► 1 107 divisors of 108 ──► 1 2 3 4 6 9 12 18 27 36 54 108 divisors of 109 ──► 1 109 divisors of 110 ──► 1 2 5 10 11 22 55 110 divisors of 111 ──► 1 3 37 111 divisors of 112 ──► 1 2 4 7 8 14 16 28 56 112 divisors of 113 ──► 1 113 divisors of 114 ──► 1 2 3 6 19 38 57 114 divisors of 115 ──► 1 5 23 115 divisors of 116 ──► 1 2 4 29 58 116 divisors of 117 ──► 1 3 9 13 39 117 divisors of 118 ──► 1 2 59 118 divisors of 119 ──► 1 7 17 119 divisors of 120 ──► 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120 divisors of 121 ──► 1 11 121 divisors of 122 ──► 1 2 61 122 divisors of 123 ──► 1 3 41 123 divisors of 124 ──► 1 2 4 31 62 124 divisors of 125 ──► 1 5 25 125 divisors of 126 ──► 1 2 3 6 7 9 14 18 21 42 63 126 divisors of 127 ──► 1 127 divisors of 128 ──► 1 2 4 8 16 32 64 128 divisors of 129 ──► 1 3 43 129 divisors of 130 ──► 1 2 5 10 13 26 65 130 divisors of 131 ──► 1 131 divisors of 132 ──► 1 2 3 4 6 11 12 22 33 44 66 132 divisors of 133 ──► 1 7 19 133 divisors of 134 ──► 1 2 67 134 divisors of 135 ──► 1 3 5 9 15 27 45 135 divisors of 136 ──► 1 2 4 8 17 34 68 136 divisors of 137 ──► 1 137 divisors of 138 ──► 1 2 3 6 23 46 69 138 divisors of 139 ──► 1 139 divisors of 140 ──► 1 2 4 5 7 10 14 20 28 35 70 140 divisors of 141 ──► 1 3 47 141 divisors of 142 ──► 1 2 71 142 divisors of 143 ──► 1 11 13 143 divisors of 144 ──► 1 2 3 4 6 8 9 12 16 18 24 36 48 72 144 divisors of 145 ──► 1 5 29 145 divisors of 146 ──► 1 2 73 146 divisors of 147 ──► 1 3 7 21 49 147 divisors of 148 ──► 1 2 4 37 74 148 divisors of 149 ──► 1 149 divisors of 150 ──► 1 2 3 5 6 10 15 25 30 50 75 150 divisors of 151 ──► 1 151 divisors of 152 ──► 1 2 4 8 19 38 76 152 divisors of 153 ──► 1 3 9 17 51 153 divisors of 154 ──► 1 2 7 11 14 22 77 154 divisors of 155 ──► 1 5 31 155 divisors of 156 ──► 1 2 3 4 6 12 13 26 39 52 78 156 divisors of 157 ──► 1 157 divisors of 158 ──► 1 2 79 158 divisors of 159 ──► 1 3 53 159 divisors of 160 ──► 1 2 4 5 8 10 16 20 32 40 80 160 divisors of 161 ──► 1 7 23 161 divisors of 162 ──► 1 2 3 6 9 18 27 54 81 162 divisors of 163 ──► 1 163 divisors of 164 ──► 1 2 4 41 82 164 divisors of 165 ──► 1 3 5 11 15 33 55 165 divisors of 166 ──► 1 2 83 166 divisors of 167 ──► 1 167 divisors of 168 ──► 1 2 3 4 6 7 8 12 14 21 24 28 42 56 84 168 divisors of 169 ──► 1 13 169 divisors of 170 ──► 1 2 5 10 17 34 85 170 divisors of 171 ──► 1 3 9 19 57 171 divisors of 172 ──► 1 2 4 43 86 172 divisors of 173 ──► 1 173 divisors of 174 ──► 1 2 3 6 29 58 87 174 divisors of 175 ──► 1 5 7 25 35 175 divisors of 176 ──► 1 2 4 8 11 16 22 44 88 176 divisors of 177 ──► 1 3 59 177 divisors of 178 ──► 1 2 89 178 divisors of 179 ──► 1 179 divisors of 180 ──► 1 2 3 4 5 6 9 10 12 15 18 20 30 36 45 60 90 180 divisors of 181 ──► 1 181 divisors of 182 ──► 1 2 7 13 14 26 91 182 divisors of 183 ──► 1 3 61 183 divisors of 184 ──► 1 2 4 8 23 46 92 184 divisors of 185 ──► 1 5 37 185 divisors of 186 ──► 1 2 3 6 31 62 93 186 divisors of 187 ──► 1 11 17 187 divisors of 188 ──► 1 2 4 47 94 188 divisors of 189 ──► 1 3 7 9 21 27 63 189 divisors of 190 ──► 1 2 5 10 19 38 95 190 divisors of 191 ──► 1 191 divisors of 192 ──► 1 2 3 4 6 8 12 16 24 32 48 64 96 192 divisors of 193 ──► 1 193 divisors of 194 ──► 1 2 97 194 divisors of 195 ──► 1 3 5 13 15 39 65 195 divisors of 196 ──► 1 2 4 7 14 28 49 98 196 divisors of 197 ──► 1 197 divisors of 198 ──► 1 2 3 6 9 11 18 22 33 66 99 198 divisors of 199 ──► 1 199 divisors of 200 ──► 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] ## 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 factor(n:Int) = (1 to Math.sqrt(n)).filter(n%_== 0).flatMap(x=>List(n/x,x)).toList.sort(_>_) ## 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)  ## 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;

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


## Slate

n@(Integer traits) primeFactors[  [| :result |   result nextPut: 1.   n primesDo: [| :prime | result nextPut: prime]] writingAs: {}].

where primesDo: is a part of the standard numerics library:

n@(Integer traits) primesDo: block"Decomposes the Integer into primes, applying the block to each (in increasingorder)."[| div next remaining |  div: 2.  next: 3.  remaining: n.  [[(remaining \\ div) isZero]     whileTrue:       [block applyTo: {div}.	remaining: remaining // div].   remaining = 1] whileFalse:     [div: next.      next: next + 2] "Just looks at the next odd integer."].

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

output

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

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