Factors of an integer: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Mercury}}: Eliminated the need for checks on bad arguments.)
m (whitespace)
Line 17: Line 17:


=={{header|Ada}}==
=={{header|Ada}}==

<lang Ada>with Ada.Text_IO;
<lang Ada>with Ada.Text_IO;
with Ada.Command_Line;
with Ada.Command_Line;
Line 42: Line 41:


=={{header|Aikido}}==
=={{header|Aikido}}==
<lang aikido>
<lang aikido>import math
import math


function factor (n:int) {
function factor (n:int) {
Line 76: Line 74:
printvec (factor (45))
printvec (factor (45))
printvec (factor (25))
printvec (factor (25))
printvec (factor (100))
printvec (factor (100))</lang>


</lang>


=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
Line 122: Line 117:


=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==

<lang AutoHotkey>msgbox, % factors(45) "`n" factors(53) "`n" factors(64)
<lang AutoHotkey>msgbox, % factors(45) "`n" factors(53) "`n" factors(64)


Line 151: Line 145:
Next
Next
Return $ls_factors&$intg
Return $ls_factors&$intg
EndFunc
EndFunc</lang>
</lang>
<pre>
<pre>
Output:
Output:
Line 160: Line 153:


=={{header|BASIC}}==
=={{header|BASIC}}==

{{works with|QBasic}}
{{works with|QBasic}}

This example stores the factors in a shared array (with the original number as the last element) for later retrieval.
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).
Note that this will error out if you pass 32767 (or higher).

<lang qbasic>DECLARE SUB factor (what AS INTEGER)
<lang qbasic>DECLARE SUB factor (what AS INTEGER)


Line 249: Line 239:


Interactive version:
Interactive version:

<lang dos>@echo off
<lang dos>@echo off
set /p limit=Gimme a number:
set /p limit=Gimme a number:
Line 297: Line 286:
L$ += STR$(L%(I%)) + ", "
L$ += STR$(L%(I%)) + ", "
NEXT
NEXT
= LEFT$(LEFT$(L$))
= LEFT$(LEFT$(L$))</lang>
</lang>
Output:
Output:
<pre>The factors of 45 are 1, 3, 5, 9, 15, 45
<pre>The factors of 45 are 1, 3, 5, 9, 15, 45
Line 524: Line 512:
Console.WriteLine(String.Join(", ", 45.Factors()));
Console.WriteLine(String.Join(", ", 45.Factors()));
}
}
}</lang>
}
</lang>


C# 1.0
C# 1.0

<lang csharp>static void Main(string[] args)
<lang csharp>static void Main(string[] args)
{
{
Line 556: Line 542:
Console.WriteLine("Done.");
Console.WriteLine("Done.");
} while (true);
} while (true);
}</lang>
}
</lang>


Example output:
Example output:
Line 568: Line 553:


=={{header|Clojure}}==
=={{header|Clojure}}==

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


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.
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]
<lang lisp>(defn factors [n]
(into (sorted-set)
(into (sorted-set)
Line 583: Line 566:


Same idea, using for comprehensions.
Same idea, using for comprehensions.

<lang lisp>(defn factors [n]
<lang lisp>(defn factors [n]
(into (sorted-set)
(into (sorted-set)
Line 591: Line 573:


=={{header|CoffeeScript}}==
=={{header|CoffeeScript}}==
<lang coffeescript>
<lang coffeescript># Reference implementation for finding factors is slow, but hopefully
# Reference implementation for finding factors is slow, but hopefully
# robust--we'll use it to verify the more complicated (but hopefully faster)
# robust--we'll use it to verify the more complicated (but hopefully faster)
# algorithm.
# algorithm.
Line 650: Line 631:
console.log n, factors
console.log n, factors
if n < 1000000
if n < 1000000
verify_factors factors, n
verify_factors factors, n</lang>
</lang>
output
output
<lang coffeescript>> coffee factors.coffee
<lang>
> coffee factors.coffee
1 [ 1 ]
1 [ 1 ]
3 [ 1, 3 ]
3 [ 1, 3 ]
Line 674: Line 653:
11111111111,
11111111111,
33333333333,
33333333333,
99999999999 ]
99999999999 ]</lang>
</lang>



=={{header|Common Lisp}}==
=={{header|Common Lisp}}==

We iterate in the range <code>1..sqrt(n)</code> collecting ‘low’ factors and corresponding ‘high’ factors, and combine at the end to produce an ordered list of factors.
We iterate in the range <code>1..sqrt(n)</code> collecting ‘low’ factors and corresponding ‘high’ factors, and combine at the end to produce an ordered list of factors.

<lang lisp>(defun factors (n &aux (lows '()) (highs '()))
<lang lisp>(defun factors (n &aux (lows '()) (highs '()))
(do ((limit (isqrt n)) (factor 1 (1+ factor)))
(do ((limit (isqrt n)) (factor 1 (1+ factor)))
Line 723: Line 698:
[1, 239, 4649, 1111111]</pre>
[1, 239, 4649, 1111111]</pre>
Functional style:
Functional style:

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


Line 737: Line 711:


=={{header|E}}==
=={{header|E}}==

{{improve|E|Use a cleverer algorithm such as in the Common Lisp example.}}
{{improve|E|Use a cleverer algorithm such as in the Common Lisp example.}}

<lang e>def factors(x :(int > 0)) {
<lang e>def factors(x :(int > 0)) {
var xfactors := []
var xfactors := []
Line 747: Line 719:
return xfactors
return xfactors
}</lang>
}</lang>



=={{header|Ela}}==
=={{header|Ela}}==


===Using higher-order function===
===Using higher-order function===

<lang ela>open Core
<lang ela>open Core


Line 758: Line 728:


===Using comprehension===
===Using comprehension===

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


Line 796: Line 765:
64 .factors
64 .factors
100 .factors</lang>
100 .factors</lang>



=={{Header|Fortran}}==
=={{Header|Fortran}}==
Line 820: Line 788:
end program</lang>
end program</lang>

=={{header|GAP}}==
=={{header|GAP}}==
<lang gap># Built-in function
<lang gap># Built-in function
Line 841: Line 810:
div2(Factorial(5));
div2(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]</lang>
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]</lang>

=={{header|Go}}==
=={{header|Go}}==
Trial division, no prime number generator, but with some optimizations. It's good enough to factor any 64 bit integer, with large primes taking several seconds.
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.
Line 942: Line 912:
Test:
Test:
<lang groovy>((1..30) + [333333]).each { println ([number:it, factors:factorize(it)]) }</lang>
<lang groovy>((1..30) + [333333]).each { println ([number:it, factors:factorize(it)]) }</lang>

Output:
Output:
<pre>[number:1, factors:[1]]
<pre>[number:1, factors:[1]]
Line 978: Line 947:
=={{Header|Haskell}}==
=={{Header|Haskell}}==
Using D. Amos module Primes [http://www.polyomino.f2s.com/david/haskell/codeindex.html] for finding prime factors
Using D. Amos module Primes [http://www.polyomino.f2s.com/david/haskell/codeindex.html] for finding prime factors
<lang Haskell>
<lang Haskell>import HFM.Primes(primePowerFactors)
import HFM.Primes(primePowerFactors)
import Data.List
import Data.List


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


=={{header|HicEst}}==
=={{header|HicEst}}==
Line 1,012: Line 979:


=={{header|J}}==
=={{header|J}}==

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

<lang J>q: 40
<lang J>q: 40
2 2 2 5</lang>
2 2 2 5</lang>


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

<lang J>__ q: 40
<lang J>__ q: 40
2 5
2 5
Line 1,025: Line 989:


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

<lang J>((^ i.@>:)&.>/) __ q: 40</lang>
<lang J>((^ i.@>:)&.>/) __ q: 40</lang>
┌───────┬───┐
┌───────┬───┐
Line 1,032: Line 995:


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

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


Line 1,042: Line 1,004:


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

<lang J>
factors=: monad define
Y=. y"_
Y=. y"_
/:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y
/:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y
Line 1,113: Line 1,073:
/ Number of factors for 3491888400 .. 3491888409
/ Number of factors for 3491888400 .. 3491888409
#:'f' 3491888400+!10
#:'f' 3491888400+!10
1920 16 4 4 12 16 32 16 8 24
1920 16 4 4 12 16 32 16 8 24</lang>
</lang>


=={{header|Liberty BASIC}}==
=={{header|Liberty BASIC}}==
<lang lb>num = 10677106534462215678539721403561279
<lang lb>
num = 10677106534462215678539721403561279
maxnFactors = 1000
maxnFactors = 1000
dim primeFactors(maxnFactors), nPrimeFactors(maxnFactors)
dim primeFactors(maxnFactors), nPrimeFactors(maxnFactors)
Line 1,190: Line 1,148:
next i
next i
end if
end if
end function
end function</lang>
</lang>


Outcome:
Outcome:
<lang lb>Start finding all factors of 10677106534462215678539721403561279:

<lang lb>

Start finding all factors of 10677106534462215678539721403561279:
10677106534462215678539721403561279 = 29269^1 * 32579^1 * 98731^2 * 104729^3
10677106534462215678539721403561279 = 29269^1 * 32579^1 * 98731^2 * 104729^3
1 1
1 1
Line 1,247: Line 1,201:
47 364792324112959639158827476291
47 364792324112959639158827476291
48 10677106534462215678539721403561279
48 10677106534462215678539721403561279
done
done</lang>

</lang>


=={{header|Logo}}==
=={{header|Logo}}==
Line 1,257: Line 1,209:


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

=={{header|Lua}}==
=={{header|Lua}}==
<lang lua>function Factors( n )
<lang lua>function Factors( n )
Line 1,273: Line 1,226:
=={{header|Mathematica}}==
=={{header|Mathematica}}==
<lang Mathematica>Factorize[n_Integer] := Divisors[n]</lang>
<lang Mathematica>Factorize[n_Integer] := Divisors[n]</lang>



=={{header|MATLAB}} / {{header|Octave}}==
=={{header|MATLAB}} / {{header|Octave}}==

<lang Matlab> function fact(n);
<lang Matlab> function fact(n);
f = factor(n); % prime decomposition
f = factor(n); % prime decomposition
Line 1,307: Line 1,258:


=={{header|Maxima}}==
=={{header|Maxima}}==

The builtin <code>divisors</code> function does this.
The builtin <code>divisors</code> function does this.

<lang maxima>(%i96) divisors(100);
<lang maxima>(%i96) divisors(100);
(%o96) {1,2,4,5,10,20,25,50,100}</lang>
(%o96) {1,2,4,5,10,20,25,50,100}</lang>


Such a function could be implemented like so:
Such a function could be implemented like so:

<lang maxima>divisors2(n) := map( lambda([l], lreduce("*", l)),
<lang maxima>divisors2(n) := map( lambda([l], lreduce("*", l)),
apply( cartesian_product,
apply( cartesian_product,
Line 1,393: Line 1,341:


=={{header|Niue}}==
=={{header|Niue}}==
<lang Niue>[ 'n ; [ negative-or-zero [ , ] if

<lang Niue>
[ 'n ; [ negative-or-zero [ , ] if
[ n not-factor [ , ] when ] else ] n times n ] 'factors ;
[ n not-factor [ , ] when ] else ] n times n ] 'factors ;


Line 1,405: Line 1,351:
53 factors .s .clr ( => 1 53 ) newline
53 factors .s .clr ( => 1 53 ) newline
64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline
64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline
12 factors .s .clr ( => 1 2 3 4 6 12 )
12 factors .s .clr ( => 1 2 3 4 6 12 ) </lang>
</lang>


=={{header|Objeck}}==
=={{header|Objeck}}==
<lang objeck>
<lang objeck>use IO;
use IO;
use Structure;
use Structure;


Line 1,447: Line 1,391:
}
}
}
}
}</lang>
}
</lang>


=={{header|OCaml}}==
=={{header|OCaml}}==
Line 1,482: Line 1,425:


=={{header|Pascal}}==
=={{header|Pascal}}==
Based on the Fortran example:
{{trans|Fortran}}
<lang pascal>program Factors;
<lang pascal>program Factors;
var
var
Line 1,522: Line 1,465:
=={{header|Perl 6}}==
=={{header|Perl 6}}==
{{works with|Rakudo Star|2010-08}}
{{works with|Rakudo Star|2010-08}}

<lang perl6>sub factors (Int $n) {
<lang perl6>sub factors (Int $n) {
sort +*, keys hash
sort +*, keys hash
Line 1,531: Line 1,473:


=={{header|PHP}}==
=={{header|PHP}}==
<lang PHP>
<lang PHP>function GetFactors($n){
function GetFactors($n){
$factors = array(1, $n);
$factors = array(1, $n);
for($i = 2; $i * $i <= $n; $i++){
for($i = 2; $i * $i <= $n; $i++){
Line 1,552: Line 1,493:


=={{header|PL/I}}==
=={{header|PL/I}}==
<lang PL/I>
<lang PL/I>do i = 1 to n;
do i = 1 to n;
if mod(n, i) = 0 then put skip list (i);
if mod(n, i) = 0 then put skip list (i);
end;
end;</lang>
</lang>


=={{header|PowerShell}}==
=={{header|PowerShell}}==
Line 1,605: Line 1,544:
;
;
sort(LC, L)
sort(LC, L)
).
).</lang>
</lang>
Output :
Output :
<pre> ?- factor(36, L).
<pre> ?- factor(36, L).
Line 1,677: Line 1,615:
64: factors: [1, 2, 4, 8, 16, 32, 64]</lang>
64: factors: [1, 2, 4, 8, 16, 32, 64]</lang>


More efficient when factoring many numbers:<lang python>def factor(n):
More efficient when factoring many numbers:
<lang python>def factor(n):
a, r = 1, [1]
a, r = 1, [1]
while a * a < n:
while a * a < n:
Line 1,692: Line 1,631:


=={{header|R}}==
=={{header|R}}==
<lang R>
<lang R>factors <- function(n)
factors <- function(n)
{
{
if(length(n) > 1)
if(length(n) > 1)
Line 1,704: Line 1,642:
}
}
}
}
factors(60)
factors(60)</lang>
</lang>
1 2 3 4 5 6 10 12 15 20 30 60
1 2 3 4 5 6 10 12 15 20 30 60
<lang R>
<lang R>factors(c(45, 53, 64))</lang>
factors(c(45, 53, 64))
</lang>
<pre>
<pre>
[[1]]
[[1]]
Line 1,735: Line 1,670:


=={{header|REXX}}==
=={{header|REXX}}==
<lang rexx>/*REXX program to calculate & show divisors of positive integer(s). */
<lang rexx>
/*REXX program to calculate & show divisors of positive integer(s). */
parse arg low high .; if high=='' then high=low
parse arg low high .; if high=='' then high=low


Line 1,769: Line 1,703:
else p.2=arg(k) p.2 /*build (descending) to "high" list.*/
else p.2=arg(k) p.2 /*build (descending) to "high" list.*/
end
end
return
return</lang>
</lang>
Below is the output for the divisors for the first two hundred integers
Below is the output for the divisors for the first two hundred integers
when
when
<br><br>
<pre>
1 200
1 200
<br><br>
</pre>
is entred as arguments.
is entred as arguments.
<pre style="height:30ex;overflow:scroll">
<pre style="height:30ex;overflow:scroll">
Line 1,981: Line 1,914:


=={{header|Ruby}}==
=={{header|Ruby}}==

<lang ruby>class Integer
<lang ruby>class Integer
def factors() (1..self).select { |n| (self % n).zero? } end
def factors() (1..self).select { |n| (self % n).zero? } end
Line 2,037: Line 1,969:


=={{header|Scala}}==
=={{header|Scala}}==
<lang scala>def factor(n:Int) = (1 to Math.sqrt(n)).filter(n%_== 0).flatMap(x=>List(n/x,x)).toList.sort(_>_)</lang>
<lang scala>
def factor(n:Int) = (1 to Math.sqrt(n)).filter(n%_== 0).flatMap(x=>List(n/x,x)).toList.sort(_>_)
</lang>


=={{header|Scheme}}==
=={{header|Scheme}}==
Line 2,056: Line 1,986:


=={{header|Slate}}==
=={{header|Slate}}==
<lang slate>
<lang slate>n@(Integer traits) primeFactors
n@(Integer traits) primeFactors
[
[
[| :result |
[| :result |
result nextPut: 1.
result nextPut: 1.
n primesDo: [| :prime | result nextPut: prime]] writingAs: {}
n primesDo: [| :prime | result nextPut: prime]] writingAs: {}
].
].</lang>
</lang>
where <tt>primesDo:</tt> is a part of the standard numerics library:
where <tt>primesDo:</tt> is a part of the standard numerics library:
<lang slate>
<lang slate>n@(Integer traits) primesDo: block
n@(Integer traits) primesDo: block
"Decomposes the Integer into primes, applying the block to each (in increasing
"Decomposes the Integer into primes, applying the block to each (in increasing
order)."
order)."
Line 2,080: Line 2,007:
[div: next.
[div: next.
next: next + 2] "Just looks at the next odd integer."
next: next + 2] "Just looks at the next odd integer."
].
].</lang>
</lang>


=={{header|Tcl}}==
=={{header|Tcl}}==

Revision as of 17:06, 29 January 2012

Task
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 | Comparison | Matching

Memory Operations
Pointers & references | Addresses

Compute the factors of a number. The factors of a positive integer are those positive integers by which it 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.

See also:

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);
  1. FOR INT j IN # gen factors(num, # ) DO ( #
    1. (INT j)VOID:(
      print((sep,whole(j,0))); 
      sep:=", "
  1. 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

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

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>

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

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

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

<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

C

<lang c>#include <stdio.h>

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

  1. include <stdlib.h>
  2. 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 *(ulong*)a < *(ulong*)b ? -1 : *(ulong*)a > *(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>

  1. include <vector>
  2. include <algorithm>
  3. 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>

Example output:

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

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

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

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

CoffeeScript

<lang coffeescript># Reference implementation for finding factors is slow, but hopefully

  1. robust--we'll use it to verify the more complicated (but hopefully faster)
  2. algorithm.

slow_factors = (n) ->

 (i for i in [1..n] when n % i == 0)
 
  1. The rest of this code does two optimizations:
  2. 1) When you find a prime factor, divide it out of n (smallest_prime_factor).
  3. 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 <lang coffeescript>> 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 ]</lang>

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

D

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

}</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 filter!(i => n % i == 0)(iota(1, n+1));

}

void main() {

   writeln(factors(36));

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

Ela

Using higher-order function

<lang ela>open Core

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

Using comprehension

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

Erlang

<lang erlang>factors(N) ->

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

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

<lang false>[1[\$@$@-][\$@$@$@$@\/*=[$." "]?1+]#.%]f: 45f;! 53f;! 64f;!</lang>

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>

GAP

<lang gap># Built-in function DivisorsInt(Factorial(5));

  1. [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]
  1. A possible implementation, not suitable to large n

div := n -> Filtered([1 .. n], k -> n mod k = 0);

div(Factorial(5));

  1. [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]
  1. 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. [ 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>

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> 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. <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: 40

2 5
3 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: 40</lang>

┌───────┬───┐
│1 2 4 8│1 5│
└───────┴───┘

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

<lang J>factors 40

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

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

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

)</lang>

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

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

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

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>

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>

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

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

Mathematica

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

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.

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.

fac.m

<lang Mercury>:- module fac.

- interface.
- import_module io.
- pred main(io::di, io::uo) is det.
- implementation.
- import_module float, getopt, 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, L) :-

       Limit = float.truncate_to_int(math.sqrt(float(N))),

factor(N, 2, Limit, [1,N], L).

- pred factor(int::in, int::in, int::in, list(int)::in, list(int)::out) is det.

factor(N, X, Z, LC, L) :-

   (X  > Z ->
       list.sort_and_remove_dups(LC, L)
   ;
       (0 = N mod X ->
           factor(N, X + 1, Z, [X, N / X | LC], L)
       ;
           factor(N, X + 1, Z, LC, L)
       )
   ).
- func factor(int::in) = (list(int)::out) is det.

factor(N) = L :- factor(N, L).</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])

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>

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>

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>

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>

Pascal

Translation of: Fortran

<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 

Perl

<lang perl>sub factors {

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

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

Perl 6

Works with: Rakudo Star version 2010-08

<lang perl6>sub factors (Int $n) {

   sort +*, keys hash
       map { $^x => 1, $n div $^x => 1 },
       grep { $n %% $^x },
       1 .. ceiling sqrt $n;

}</lang>

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

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

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

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

<lang rexx>/*REXX program to calculate & show divisors of positive integer(s). */ parse arg low high .; if high== then high=low

 do j=low to high
 say 'n='right(j,6) "divisors="divs(j)
 end

exit


/*------------------------------DIVS subroutine---------------------*/ divs: procedure; parse arg x . if x==1 then return 1 /*hand special case of unity (1). */ p.= /*initilize P.1 & P.2 lists to empty*/

 do j=2                        /*divide by all divisors < sqrt(x). */
 if j*j>=x then leave          /*at sqrt(x) or greater?  Then stop.*/
 if x//j==0 then call divAdd j,x%j    /*Divisible?  Add 2 divisors.*/
 end

if j*j==x then call divAdd j /*test for special case: a square. */

                               /*up to this point, we just have    */
                               /*calculated the proper divisors.   */

return space(1 p.1 p.2 x) /*return divisors: 1, both lists, x */

/*------------------------------DIVADD subroutine-------------------*/ divAdd: arg a,b /*add to "low" and/or "high" lists. */

 do k=1 for arg()
 if k==1 then p.1=p.1 arg(k)   /*append (ascending) to  "low" list.*/
         else p.2=arg(k) p.2   /*build (descending) to "high" list.*/
 end

return</lang> Below is the output for the divisors for the first two hundred integers when

1  200

is entred as arguments.

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

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 , we can write <lang ruby>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
 end

end [45, 53, 64].each {|n| p n.factors}</lang> output

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

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

<lang scala>def factor(n:Int) = (1 to Math.sqrt(n)).filter(n%_== 0).flatMap(x=>List(n/x,x)).toList.sort(_>_)</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)

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>

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

Ursala

The simple way: <lang Ursala>#import std

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