Factors of an integer
From Rosetta Code
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
Pointers & references |
Addresses
Compute the factors of a positive integer. These factors are the positive integers by which the number being factored can be divided to yield a positive integer result (though the concepts function correctly for zero and negative integers, the set of factors of zero 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:
[edit] 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))
[edit] 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;
}
[edit] 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;
[edit] 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))
[edit] ALGOL 68
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
[edit] 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
[edit] 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
Output: Factors of 45 are: 1, 3, 5, 9, 15, 45
[edit] BASIC
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);
NEXT
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
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
[edit] Batch File
Command line version:
@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
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 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
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
[edit] 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
[edit] 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;
}
[edit] Prime factoring
#include <stdio.h>output
#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 *(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;
}
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
[edit] 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;
}
}
[edit] 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.
[edit] 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 (sqrt n)))) )))
Same idea, using for comprehensions.
(defn factors [n]
(into (sorted-set)
(reduce concat
(for [x (range 1 (inc (sqrt n))) :when (zero? (rem n x))]
[x (/ n x)]))))
[edit] 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 ]
[edit] 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)))))
[edit] D
[edit] 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]
[edit] 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]
[edit] E
def factors(x :(int > 0)) {
var xfactors := []
for f ? (x % f <=> 0) in 1..x {
xfactors with= f
}
return xfactors
}
[edit] Ela
[edit] Using higher-order function
open Core
let factors m = filter (\x -> m % x == 0) [1..m]
[edit] Using comprehension
let factors m = [x \\ x <- [1..m] | m % x == 0]
[edit] Erlang
factors(N) ->
[I || I <- lists:seq(1,N div 2), N rem I == 0]++[N].
[edit] 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
}
[edit] Factor
USE: math.primes.factors
( scratchpad ) 24 divisors .
{ 1 2 3 4 6 8 12 24 }
[edit] FALSE
[1[\$@$@-][\$@$@$@$@\/*=[$." "]?1+]#.%]f:
45f;! 53f;! 64f;!
[edit] 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 .factors
53 .factors
64 .factors
100 .factors
[edit] 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
[edit] GAP
# Built-in function
DivisorsInt(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]
# A possible implementation, not suitable to large n
div := n -> Filtered([1 .. n], k -> n mod k = 0);
div(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]
# Another implementation, usable for large n (if n can be factored quickly)
div2 := function(n)
local f, p;
f := Collected(FactorsInt(n));
p := List(f, v -> List([0 .. v[2]], k -> v[1]^k));
return SortedList(List(Cartesian(p), Product));
end;
div2(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]
[edit] 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
[edit] 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]]
[edit] 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
[edit] 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
[edit] Icon and Unicon
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
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 100divisors
[edit] 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: 40
2 5
3 1
With this, we can form lists of each of the potential relevant powers of each of these prime factors
((^ i.@>:)&.>/) __ q: 40
┌───────┬───┐ │1 2 4 8│1 5│ └───────┴───┘
From here, it's a simple matter (*/&>@{) to compute all possible factors of the original number
factors=: */&>@{@((^ i.@>:)&.>/)@q:~&__
factors 40
1 5
2 10
4 20
8 40
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:
factors=: monad define
Y=. y"_
/:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y
)
A less efficient, but concise variation on this theme:
~.,*/&> { 1 ,&.> q: 40
1 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.
factors 40
1 2 4 5 8 10 20 40
[edit] Java
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;
}
[edit] 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]
[edit] 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
[edit] Liberty BASIC
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
Outcome:
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
[edit] Logo
to factors :n
output filter [equal? 0 modulo :n ?] iseq 1 :n
end
show factors 28 ; [1 2 4 7 14 28]
[edit] 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
[edit] Mathematica
Factorize[n_Integer] := Divisors[n]
[edit] 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
[edit] 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))));
[edit] 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:
- The input number itself and 1 are both considered factors.
- The numbers between 2 and the square root of the input number are checked for even division.
- If the incremental number divides evenly into the input number, both the incremental number and the quotient are added to the list of factors.
Note that this implementation is tail-recursive and uses tricks of unification to "magically" pull the "L" variable seemingly out of thin air.
[edit] 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, L) :-
Limit = float.truncate_to_int(math.sqrt(float(N))),
factor(N, 2, Limit, L0),
list.sort_and_remove_dups([1, N | L0], L).
:- pred factor(int::in, int::in, int::in, list(int)::out) is det.
factor(N, X, Z, L0) :-
(X > Z ->
L0 = []
;
(0 = N mod X ->
L0 = [X, N / X | L]
;
L0 = L
),
factor(N, X + 1, Z, L)
).
:- func factor(int::in) = (list(int)::out) is det.
factor(N) = L :- factor(N, L).
[edit] 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])
[edit] 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]
[edit] 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 )
[edit] 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();
};
}
}
}
[edit] OCaml
let rec range = function 0 -> [] | n -> range(n-1) @ [n]
let factors n =
List.filter (fun v -> (n mod v) = 0) (range n)
[edit] 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}}
[edit] PARI/GP
divisors(n)
[edit] 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.
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
[edit] Perl
sub factors
{
my($n) = @_;
return grep { $n % $_ == 0 }(1 .. $n);
}
print join ' ',factors(64);
[edit] Perl 6
sub factors (Int $n) {
sort +*, keys hash
map { $^x => 1, $n div $^x => 1 },
grep { $n %% $^x },
1 .. ceiling sqrt $n;
}
[edit] 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;
}
[edit] PicoLisp
(de factors (N)
(filter
'((D) (=0 (% N D)))
(range 1 N) ) )
[edit] PL/I
do i = 1 to n;
if mod(n, i) = 0 then put skip list (i);
end;
[edit] PowerShell
[edit] 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.
[edit] A little more clever
function Get-Factor ($a) {
1..[Math]::Sqrt($a) `
| Where-Object { $a % $_ -eq 0 } `
| ForEach-Object { $_; $a / $_ } `
| Sort-Object -Unique
}
Here the range of integers is only taken up to the square root of the number, the same filtering applies. Afterwards the corresponding larger factors are calculated and sent down the pipeline along with the small ones found earlier.
[edit] ProDOS
Uses the math module:
editvar /newvar /value=a /userinput=1 /title=Enter an integer:
do /delimspaces %% -a- >b
printline Factors of -a-: -b-
[edit] 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].
[edit] 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
Output can look like
Enter integer to factorize: 96 1 2 3 4 6 8 12 16 24 32 48 96
[edit] 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
[edit] 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
[edit] 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 result
End Function
[edit] 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
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
[edit] Ruby
class Integer
def factors() (1..self).select { |n| (self % n).zero? } end
end
p 45.factors
[1, 3, 5, 9, 15, 45]
As we only have to loop up to 
, we can write
class Integer
def factors()
1.upto(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}
output
[1, 3, 5, 9, 15, 45] [1, 53] [1, 2, 4, 8, 16, 32, 64]
[edit] 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;
[edit] Scala
def factor(n:Int) = (1 to Math.sqrt(n)).filter(n%_== 0).flatMap(x=>List(n/x,x)).toList.sort(_>_)
[edit] 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)
[edit] 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 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."
].
[edit] 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
[edit] 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>
[edit] 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
Categories:
- Programming Tasks
- Basic language learning
- Basic Data Operations
- Arithmetic operations
- Mathematical operations
- ACL2
- ActionScript
- Ada
- Aikido
- ALGOL 68
- AutoHotkey
- AutoIt
- BASIC
- Batch File
- BBC BASIC
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- D
- E
- E examples needing attention
- Examples needing attention
- Ela
- Erlang
- F Sharp
- Factor
- FALSE
- Forth
- Fortran
- GAP
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- K
- Liberty BASIC
- Logo
- Lua
- Mathematica
- MATLAB
- Octave
- Maxima
- Mercury
- MUMPS
- Niue
- Objeck
- OCaml
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PowerShell
- ProDOS
- Prolog
- PureBasic
- Python
- R
- REALbasic
- REXX
- Ruby
- Sather
- Scala
- Scheme
- Slate
- Tcl
- Ursala
- XPL0
