# [R] All the products of common factors

Stavros Macrakis macrakis at alum.mit.edu
Tue Feb 24 23:55:11 CET 2009

```On Mon, Feb 23, 2009 at 9:52 PM, Fox, Gordon <gfox at cas.usf.edu> wrote:
> This is a seemingly simple problem - hopefully someone can help.
> Problem: we have two integers. We want (1) all the common factors, and
> (2) all the possible products of these factors. We know how to get (1),
> but can't figure out a general way to get (2).

Your problem statement is rather complicated, but I believe it reduces
to simply:

Find the factors of the greatest common divisor of A and B.

Note: *factors*, not *prime factors*.  Finding the prime factors first
is unnecessary.

Euclid's algorithm straightforwardly finds GCDs:

gcd <- function(a,b) {if (a>b) gcd(b,a) else if (a==0) b else gcd(a,b%%a)}
gcd(40,80) => 40

Now find all the factors of 40.  Might as well use a simple, naive
algorithm for such small numbers:

num <- 40
which(num/1:num == floor(num/1:num))
  1  2  4  5  8 10 20 40

Or if you want to get really fancy and efficient:

smallfacs <-  which( (q <- num/1:sqrt(num)) == floor(q) )
c(smallfacs,rev(num/smallfacs))

You do *not* need to factor the original numbers.  You do *not* need
to iterate through combinations.

complicated and inefficient code...:

system.time({commfac <- c(1,rep(2,20))   # about 1e6
cfun <- function(i) { combn(commfac,i,prod) }
L <- lapply(as.list(1:length(commfac)),cfun)
unique(sort(unlist(L)))})
user  system elapsed
24.71    0.01   24.89
> system.time({num <- 2^20; which(num/1:num == floor(num/1:num))})
user  system elapsed
0.17    0.00    0.17

> num <- prod(1:16)
> format(num,digits=20)
 "20922789888000"
> system.time( { smallfacs <-  which( (q <- num/1:sqrt(num)) == floor(q) ); c(smallfacs,rev(num/smallfacs))})
user  system elapsed
0.64    0.06    0.70

Hope this helps,

-s

```