Factors of an integer

From Rosetta Code

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.

[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] 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] 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 = (int *)realloc( fctrs->list, newSize * sizeof(int));
    }
    else {
        fctrs->list = (int *)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;
    if (fctrs->list) 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] C++

#include <iostream>
#include <vector>
#include <algorithm>
 
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] 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] 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

int[]factors(int num) {
        int[]ret;
        for(n=1;n<=num;n++) if (num%n==0) ret ~= n;
}

[edit] E

This example is in need of improvement:

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

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

[edit] Erlang

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

[edit] F#

let factors n = [for i in 1..n do if n%i=0 then yield i]

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

factors 40
1 2 4 5 8 10 20 40

[edit] Java

Works with: Java version 1.5+

public static TreeSet<Long> factors(long n){
	TreeSet<Long> factors = new TreeSet<Long>();
	factors.add(n); factors.add(1L);
	for(long test = n - 1; test >= Math.sqrt(n); test--){
		if(n % test == 0){
			factors.add(test);
			factors.add(n / test);
		}
	}
	return factors;
}

[edit] JavaScript

function factors(num) {
    var factors = new Array();
    var sqrt = Math.floor(Math.sqrt(num)); 
    for (var i = 1; i <= sqrt; i++) {
        if (num % i == 0) {
            factors.push(i);
            if (num / i != i) 
                factors.push(num / i);
        }
    }
    factors.sort(function(a,b){return a-b});  // numeric sort
    return factors;
}
 
factors(45);  // [1,3,5,9,15,45] 
factors(53);  // [1,53] 
factors(64);  // [1,2,4,8,16,32,64]

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

Works with: Rakudo version #22 "Thousand Oaks"

sub factors (Int $n) {
    sort +*, keys hash
        map { $^x => 1, $n div $^x => 1 },
        grep { $n !% $^x },
        1 .. ceiling sqrt $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] Perl

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

[edit] PicoLisp

(de factors (N)
   (filter
      '((D) (=0 (% N D)))
      (range 1 N) ) )

[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 ceil, sqrt
>>> def factor(n):
      return sorted(set(sum( ([x,n/x] for x in range(1, ceil(sqrt(n)) + 1) if not n%x), [] )))
 
>>> 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]

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

class Integer
  def factors()
    1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i| 
      f << i
      f << self/i unless i == self/i
      f
    end.sort
  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] 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]